Document Open Access Logo

On the Computational Hardness Needed for Quantum Cryptography

Authors Zvika Brakerski , Ran Canetti , Luowen Qian

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.24.pdf
  • Filesize: 0.81 MB
  • 21 pages

Document Identifiers

Author Details

Zvika Brakerski
  • Weizmann Institute of Science, Rehovot, Israel
Ran Canetti
  • Boston University, MA, US
Luowen Qian
  • Boston University, MA, US

Funding

Ran Canetti and Luowen Qian: Supported by DARPA under Agreement No. HR00112020023.
  • Brakerski, Zvika: Supported by the Israel Science Foundation (Grant No. 3426/21), and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482).

Acknowledgements

LQ thanks Prabhanjan Ananth and Henry Yuen for the motivating discussions prior to this work. LQ is also grateful to Scott Aaronson and William Kretschmer for their insightful discussions for Section 1.2. Some of these discussions occurred while LQ was visiting the Simons Institute for the Theory of Computing. We thank Fermi Ma for his helpful comments on a preliminary version of this work.

Cite AsGet BibTex

Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.24

Abstract

In the classical model of computation, it is well established that one-way functions (OWF) are minimal for computational cryptography: They are essential for almost any cryptographic application that cannot be realized with respect to computationally unbounded adversaries. In the quantum setting, however, OWFs appear not to be essential (Kretschmer 2021; Ananth et al., Morimae and Yamakawa 2022), and the question of whether such a minimal primitive exists remains open. We consider EFI pairs - efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states. Building on the work of Yan (2022), which shows equivalence between EFI pairs and statistical commitment schemes, we show that EFI pairs are necessary for a large class of quantum-cryptographic applications. Specifically, we construct EFI pairs from minimalistic versions of commitments schemes, oblivious transfer, and general secure multiparty computation, as well as from QCZK proofs from essentially any non-trivial language. We also construct quantum computational zero knowledge (QCZK) proofs for all of QIP from any EFI pair. This suggests that, for much of quantum cryptography, EFI pairs play a similar role to that played by OWFs in the classical setting: they are simple to describe, essential, and also serve as a linchpin for demonstrating equivalence between primitives.

Subject Classification

ACM Subject Classification
  • Theory of computation → Cryptographic primitives
  • Theory of computation → Cryptographic protocols
  • Theory of computation → Computational complexity and cryptography
  • Security and privacy → Mathematical foundations of cryptography
  • Theory of computation → Quantum complexity theory
  • Theory of computation → Quantum complexity theory
Keywords
  • quantum cryptography
  • efi
  • commitment scheme
  • oblivious transfer
  • zero knowledge
  • secure multiparty computation

Metrics

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

Related Versions

References

  1. Scott Aaronson. The complexity of quantum states and transformations: From quantum money to black holes, 2016. URL: http://arxiv.org/abs/1607.05256.
  2. Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory of Computing, 9(4):143-252, 2013. URL: https://doi.org/10.4086/toc.2013.v009a004.
  3. Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 22:1-22:67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.22.
  4. Scott Aaronson, DeVon Ingram, and William Kretschmer. The acrobatics of BQP. In 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA, volume 234 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.CCC.2022.20.
  5. Scott Aaronson and Greg Kuperberg. Quantum versus classical proofs and advice. Theory of Computing, 3(7):129-157, 2007. URL: https://doi.org/10.4086/toc.2007.v003a007.
  6. Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In CRYPTO 2022, volume 13507 of LNCS, pages 208-236. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-15802-5_8.
  7. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, USA, 1st edition, 2009. Google Scholar
  8. James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. One-way functions imply secure computation in a quantum world. In CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I, volume 12825 of LNCS, pages 467-496. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-84242-0_17.
  9. Amos Beimel, Tal Malkin, and Silvio Micali. The all-or-nothing nature of two-party secure computation. In CRYPTO '99, volume 1666 of LNCS, pages 80-97. Springer, 1999. URL: https://doi.org/10.1007/3-540-48405-1_6.
  10. Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan Håstad, Joe Kilian, Silvio Micali, and Phillip Rogaway. Everything provable is provable in zero-knowledge. In CRYPTO '88, volume 403 of LNCS, pages 37-56. Springer, 1988. URL: https://doi.org/10.1007/0-387-34799-2_4.
  11. Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of International Conference on Computers, Systems & Signal Processing, Dec. 9-12, 1984, Bangalore, India, pages 175-179, 1984. URL: http://arxiv.org/abs/2003.06557.
  12. Charles H. Bennett, Gilles Brassard, Claude Crépeau, and Marie-Hélène Skubiszewska. Practical quantum oblivious transfer. In CRYPTO '91, volume 576 of LNCS, pages 351-366. Springer, 1991. URL: https://doi.org/10.1007/3-540-46766-1_29.
  13. Nir Bitansky and Zvika Brakerski. Classical binding for quantum commitments. In TCC, volume 13042 of LNCS, pages 273-298. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-90459-3_10.
  14. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudorandom bits. SIAM Journal on Computing, 13(4):850-864, 1984. URL: https://doi.org/10.1137/0213053.
  15. Adam Bouland, Bill Fefferman, and Umesh V. Vazirani. Computational pseudorandomness, the wormhole growth paradox, and constraints on the ads/cft duality (abstract). In 11th ITCS, volume 151 of LIPIcs, pages 63:1-63:2. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.63.
  16. Zvika Brakerski, Ran Canetti, and Luowen Qian. On the computational hardness needed for quantum cryptography, 2022. URL: http://arxiv.org/abs/2209.04101.
  17. Zvika Brakerski and Omri Shmueli. (pseudo) random quantum states with binary phase. In TCC, volume 11891 of LNCS, pages 229-250. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-36030-6_10.
  18. Zvika Brakerski and Omri Shmueli. Scalable pseudorandom quantum states. In CRYPTO 2020, volume 12171 of LNCS, pages 417-440. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-56880-1_15.
  19. Fernando G.S.L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill. Models of quantum complexity growth. PRX Quantum, 2:030316, July 2021. URL: https://doi.org/10.1103/PRXQuantum.2.030316.
  20. Anne Broadbent and Alex B. Grilo. Qma-hardness of consistency of local density matrices with applications to quantum zero-knowledge. In 61st IEEE FOCS, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 196-205. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00027.
  21. Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero-knowledge proof systems for qma. SIAM Journal on Computing, 49(2):245-283, 2020. URL: https://doi.org/10.1137/18M1193530.
  22. Adam R. Brown and Leonard Susskind. Second law of quantum complexity. Phys. Rev. D, 97:086015, April 2018. URL: https://doi.org/10.1103/PhysRevD.97.086015.
  23. André Chailloux, Gus Gutoski, and Jamie Sikora. Optimal bounds for semi-honest quantum oblivious transfer. Chicago Journal of Theoretical Computer Science, 2016(13), September 2016. URL: https://doi.org/10.4086/cjtcs.2016.013.
  24. André Chailloux, Iordanis Kerenidis, and Bill Rosgen. Quantum commitments from complexity assumptions. In ICALP, volume 6755 of LNCS, pages 73-85. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22006-7_7.
  25. Claude Crépeau, Jeroen 5 Graaf, and Alain Tapp. Committed oblivious transfer and private multi-party computation. In CRYPTO '95, volume 963 of LNCS, pages 110-123. Springer, 1995. URL: https://doi.org/10.1007/3-540-44750-4_9.
  26. Claude Crépeau and Joe Kilian. Achieving oblivious transfer using weakened security assumptions (extended abstract). In 29th FOCS, White Plains, New York, USA, 24-26 October 1988, pages 42-52. IEEE Computer Society, 1988. URL: https://doi.org/10.1109/SFCS.1988.21920.
  27. Claude Crépeau, Frédéric Légaré, and Louis Salvail. How to convert the flavor of a quantum bit commitment. In - EUROCRYPT 2001, volume 2045 of LNCS, pages 60-77. Springer, 2001. URL: https://doi.org/10.1007/3-540-44987-6_5.
  28. Claude Crépeau. Quantum oblivious transfer. Journal of Modern Optics, 41(12):2445-2454, 1994. URL: https://doi.org/10.1080/09500349414552291.
  29. W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22(6):644-654, November 1976. URL: https://doi.org/10.1109/TIT.1976.1055638.
  30. Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively secure two-party evaluation of any quantum operation. In CRYPTO 2012, volume 7417 of LNCS, pages 794-811. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_46.
  31. Junbin Fang, Dominique Unruh, Jun Yan, and Dehua Zhou. How to base security on the perfect/statistical binding property of quantum bit commitment?, 2020. URL: http://arxiv.org/abs/2020/621.
  32. Oded Goldreich. A note on computational indistinguishability. Information Processing Letters, 34(6):277-281, 1990. URL: https://doi.org/10.1016/0020-0190(90)90010-U.
  33. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA, pages 25-32. ACM, 1989. URL: https://doi.org/10.1145/73007.73010.
  34. Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In 27th FOCS (sfcs 1986), pages 174-187, October 1986. URL: https://doi.org/10.1109/SFCS.1986.47.
  35. Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan. Oblivious transfer is in miniqcrypt. In - EUROCRYPT 2021, volume 12697 of LNCS, pages 531-561. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-77886-6_18.
  36. Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern. Linear growth of quantum circuit complexity. Nature Physics, 18(5):528-532, May 2022. URL: https://doi.org/10.1038/s41567-022-01539-6.
  37. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999. URL: https://doi.org/10.1137/S0097539793244708.
  38. Carl W. Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics, 1(2):231-252, June 1969. URL: https://doi.org/10.1007/BF01007479.
  39. A.S Holevo. Statistical decision theory for quantum systems. Journal of Multivariate Analysis, 3(4):337-394, 1973. URL: https://doi.org/10.1016/0047-259X(73)90028-6.
  40. R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions. In Proceedings of the Twenty-First STOC, STOC '89, pages 12-24, New York, NY, USA, 1989. ACM. URL: https://doi.org/10.1145/73007.73009.
  41. R. Impagliazzo and S. Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the Twenty-First STOC, STOC '89, pages 44-61, New York, NY, USA, 1989. ACM. URL: https://doi.org/10.1145/73007.73012.
  42. Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding cryptography on oblivious transfer - efficiently. In CRYPTO 2008, volume 5157 of LNCS, pages 572-591. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85174-5_32.
  43. Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. Qip = pspace. J. ACM, 58(6), December 2011. URL: https://doi.org/10.1145/2049697.2049704.
  44. Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In CRYPTO 2018, volume 10993 of LNCS, pages 126-152. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-96878-0_5.
  45. Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, and Tomoyuki Yamakami. Computational indistinguishability between quantum states and its cryptographic application. Journal of Cryptology, 25(3):528-555, July 2012. URL: https://doi.org/10.1007/s00145-011-9103-4.
  46. Joe Kilian. A general completeness theorem for two party games. In Proceedings of the Twenty-Third STOC, STOC '91, pages 553-560, New York, NY, USA, 1991. ACM. URL: https://doi.org/10.1145/103418.103475.
  47. Joe Kilian, Eyal Kushilevitz, Silvio Micali, and Rafail Ostrovsky. Reducibility and completeness in private computations. SIAM Journal on Computing, 29(4):1189-1208, 2000. URL: https://doi.org/10.1137/S0097539797321742.
  48. Hirotada Kobayashi. General properties of quantum zero-knowledge proofs. In TCC, volume 4948 of LNCS, pages 107-124. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_7.
  49. William Kretschmer. Quantum pseudorandomness and classical complexity. In 16th TQC, volume 197 of LIPIcs, pages 2:1-2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.TQC.2021.2.
  50. Mohammad Mahmoody and Rafael Pass. The curious case of non-interactive commitments - on the power of black-box vs. non-black-box use of primitives. In CRYPTO 2012, volume 7417 of LNCS, pages 701-718. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_41.
  51. Tomoyuki Morimae and Takashi Yamakawa. Quantum commitments and signatures without one-way functions. In CRYPTO 2022, volume 13507 of LNCS, pages 269-295. Springer, 2022. URL: https://doi.org/10.1007/978-3-031-15802-5_10.
  52. Moni Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151-158, January 1991. URL: https://doi.org/10.1007/BF00196774.
  53. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
  54. Shien Jin Ong and Salil P. Vadhan. An equivalence between zero knowledge and commitments. In TCC, volume 4948 of LNCS, pages 482-500. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-78524-8_27.
  55. R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge. In The 2nd Israel Symposium on Theory and Computing Systems, pages 3-17, Los Alamitos, CA, USA, June 1993. IEEE Computer Society. URL: https://doi.org/10.1109/ISTCS.1993.253489.
  56. RENATO RENNER. Security of quantum key distribution. International Journal of Quantum Information, 06(01):1-127, 2008. URL: https://doi.org/10.1142/S0219749908003256.
  57. Adi Shamir. On the generation of cryptographically strong pseudorandom sequences. ACM Trans. Comput. Syst., 1(1):38-44, February 1983. URL: https://doi.org/10.1145/357353.357357.
  58. Adi Shamir. Ip = pspace. J. ACM, 39(4):869-877, October 1992. URL: https://doi.org/10.1145/146585.146609.
  59. Salil P. Vadhan. An unconditional study of computational zero knowledge. SIAM Journal on Computing, 36(4):1160-1214, 2006. URL: https://doi.org/10.1137/S0097539705447207.
  60. John Watrous. Limits on the power of quantum statistical zero-knowledge. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, page 459. IEEE Computer Society, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181970.
  61. Stefan Wolf and Jürg Wullschleger. Oblivious transfer is symmetric. In EUROCRYPT 2006, volume 4004 of LNCS, pages 222-232. Springer, 2006. URL: https://doi.org/10.1007/11761679_14.
  62. Jun Yan. General properties of quantum bit commitments, 2022. URL: https://eprint.iacr.org/2020/1488.
  63. Jun Yan, Jian Weng, Dongdai Lin, and Yujuan Quan. Quantum bit commitment with application in quantum zero-knowledge proof (extended abstract). In ISAAC, volume 9472 of LNCS, pages 555-565. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48971-0_47.
  64. Andrew C. Yao. Theory and application of trapdoor functions. In 23rd FOCS (1982), pages 80-91, November 1982. URL: https://doi.org/10.1109/SFCS.1982.45.
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 Imprint Privacy Contact