Document Open Access Logo

Circuit Obfuscation Using Braids

Authors Gorjan Alagic, Stacey Jeffery, Stephen Jordan

PDF
Thumbnail PDF

File

LIPIcs.TQC.2014.141.pdf
  • Filesize: 0.67 MB
  • 20 pages

Document Identifiers

Author Details

Gorjan Alagic
Stacey Jeffery
Stephen Jordan

Cite As Get BibTex

Gorjan Alagic, Stacey Jeffery, and Stephen Jordan. Circuit Obfuscation Using Braids. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 141-160, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.TQC.2014.141

Abstract

An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.

Subject Classification

Keywords
  • obfuscation
  • cryptography
  • universality
  • quantum

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Scott Aaronson. BQP and the polynomial hierarchy. In STOC'10: Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 141-150, 2010. arXiv:0910.4698. Google Scholar
  2. Dorit Aharonov and Itai Arad. The BQP-hardness of approximating the Jones polynomial. New Journal of Physics, 13(3):035019, 2011. Google Scholar
  3. Dorit Aharonov, Michael Ben-Or, and Elad Eban. Interactive proofs for quantum computation. In Proceedings of Innovations in Computer Science (ICS 2010), pages 453-469, 2010. arXiv:0810.5375. Google Scholar
  4. G. Alagic, S. Jordan, and A. Bapat. Classical simulation of Yang-Baxter gates. To appear in: Proceedings of TQC2014. Google Scholar
  5. Gorjan Alagic, Stephen P. Jordan, Robert Koenig, and Ben W. Reichardt. Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation. Physical Review A, 82:040302(R), 2010. arXiv:1003.0923. Google Scholar
  6. Emil Artin. Theorie der Zöpfe. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 4:42-72, 1925. Google Scholar
  7. B. Barak. Can we obfuscate programs? URL: http://www.cs.princeton.edu/~boaz/Papers/obf_informal.html.
  8. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Advances in Cryptology - CRYPTO 2001, number 2139 in Lecture Notes in Computer Science, pages 1-18. Springer-Verlag, 2001. Google Scholar
  9. C. H. Bennett. Logical reversibility of computation. IBM Journal of Research and Development, 17(6):525-532, 1973. Google Scholar
  10. Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Proceedings of the 50th Annual IEEE Symposium on Fountations of Computer Science (FOCS 2008), pages 517-526, 2009. arXiv:0807.4154. Google Scholar
  11. Christian S. Collberg and Clark Thomborson. Watermarking, tamper-proofing, and obfuscation - tools for software protection. IEEE Transactions on Software Engineering, 28(8):735-746, 2002. Google Scholar
  12. H. S. M. Coxeter. Factor groups of the braid group. In Proceedings of the 4th Canadian Mathematical Congress, pages 95-122, 1959. See http://mathoverflow.net/questions/48849/. Google Scholar
  13. Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm. Quantum Information and Computation, 6(1):81-95, 2006. arXiv:quant-ph/0505030. Google Scholar
  14. Patrick Dehornoy. Efficient solutions to the braid isotopy problem. Discrete Applied Mathematics, 156:3094-3112, 2008. arxiv:math/0703666. Google Scholar
  15. D. Epstein, J. Cannon, D. Holt, S. Levy, M. Paterson, and W. Thurston. Word processing in groups. Jones and Bartlett Publ., 1992. Google Scholar
  16. Bill Fefferman and Chris Umans. Pseudorandom generators and the BQP vs. PH problem, 2010. arXiv:1007.0305. Google Scholar
  17. E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21(3/4):219-253, 1982. Google Scholar
  18. Michael H. Freedman, Michael Larsen, and Zhenghan Wang. A modular functor which is universal for quantum computation. Communications in Mathematical Physics, 227:605-622, 2002. arXiv:quant-ph/0001108. Google Scholar
  19. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 40-49, 2013. Google Scholar
  20. F. A. Garside. The braid group and other groups. Quart. J. Math. Oxford Ser., 2, 20:235-254, 1969. Google Scholar
  21. Shafi Goldwasser and Guy N. Rothblum. On best-possible obfuscation. In Theory of Cryptography - TCC 2007, pages 194-213. Springer, 2007. Google Scholar
  22. Juan González-Meneses. Basic results on braid groups, 2010. arxiv:1010.0321 [math]. Google Scholar
  23. Hessam Hamidi-Tehrani. On complexity of the word problem in braid groups and mapping class groups. Topology and its Applications, 105:237-259, 2000. Google Scholar
  24. Jarmo Hietarinta. All solutions to the constant quantum Yang-Baxter equation in two dimensions. Physics Letters A, 165:245-251, 1992. Google Scholar
  25. D. Hofheinz and R. Steinwandt. A practical attack on some braid group based cryptographic primitives. In Public Key Cryptography, pages 187-198, 2003. Google Scholar
  26. Edward V. Huntington. Sets of independent postulates for the algebra of logic. Transactions of the American Mathematical Society, 4:288-309, 1904. Google Scholar
  27. Kazuo Iwama, Yahiko Kambayashi, and Shigeru Yamashita. Transformation rules for designing CNOT-based quantum circuits. In DAC'02: Proceedings of the 39th Annual Design Automation Conference, pages 419-424, 2002. Google Scholar
  28. Dominik Janzing, Pawel Wocjan, and Thomas Beth. "Identity Check" is QMA-complete, 2003. arXiv:quant-ph/0305050. Google Scholar
  29. Stephen Jordan. Strong equivalence of reversible circuits is coNP-complete. Quantum Information and Computation, 14(15/16):1303-1308, 2014. arXiv:1307.0836. Google Scholar
  30. Louis H. Kauffman. Knots and Physics. Wold Scientific, 1991. Google Scholar
  31. A. Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303:2-30, 2003. arXiv:quant-ph/9707021. Google Scholar
  32. Hari Krovi and Alexander Russell. Quantum fourier transforms and the complexity of link invariants for quantum doubles of finite groups, 2012. arXiv:quant-ph/1210.1550 [quant-ph]. Google Scholar
  33. Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122-152, 2005. arXiv:cs/0506068. Google Scholar
  34. Carlos Mochon. Anyons from nonsolvable finite groups are sufficient for universal quantum computation. Physical Review A, 67(2):022315, 2003. arXiv:quant-ph/0206128. Google Scholar
  35. Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11/12):1053-1068, 2009. arXiv:0904.1549. Google Scholar
  36. Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000. Google Scholar
  37. R. Walter Ogburn and John Preskill. Topological quantum computation. In Quantum Computing and Quantum Communications, volume 1509 of Lecture Notes in Computer Science, pages 341-356. Springer, 1999. First NASA International Conference QCQC'98. Google Scholar
  38. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: Deniable encryption, and more. IACR Cryptology ePrint Archive, 2013:454, 2013. Google Scholar
  39. Dan Shepherd and Michael J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A, 465:1413-1439, 2009. arXiv:0809.0847. Google Scholar
  40. Peter W. Shor and Stephen P. Jordan. Estimating Jones polynomials is complete for one clean qubit. Quantum Information and Computation, 8(8/9):681-714, 2008. arXiv:0707.2831. Google Scholar
  41. Eric D. Simonaire. Sub-circuit selection and replacement algorithms modeled as term rewriting systems. Master’s thesis, Air Force Institute of Technology, 2008. Google Scholar
  42. Simon Trebst, Matthias Troyer, Zhenghan Wang, and Andreas W. W. Ludwig. A short introduction to Fibonacci anyon models. Progress in Theoretical Physics Supplement, 176:384-407, 2008. arXiv:0902.3275. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact