A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography
Authors
Sam Buxbaum, Mohammad Mahmoody
Abstract
In classical cryptography, one-way functions (OWFs) play a central role as the minimal primitive that (almost) all primitives imply. The situation is more complicated in quantum cryptography, in which honest parties and adversaries can use quantum computation and communication, and it is known that analogues of OWFs in the quantum setting might not be minimal.
In this work we ask whether OWFs are minimal for the intermediate setting of post-quantum cryptography, in which the protocols are classical while they shall resist quantum adversaries. We show that for a wide range of natural settings, if a primitive Q implies OWFs, then so does its (uniformly or non-uniformly secure) post-quantum analogue. In particular, we show that if a primitive Q implies any other primitive P that has a 2-message security game (e.g., OWFs) through a black-box classical security reduction R, then one can always (efficiently) turn any polynomial-size quantum adversary breaking P into a polynomial-size quantum adversary breaking Q. Note that this result holds even if the implementation of P using that of Q is arbitrarily non-black-box.
We also prove extensions of this result for when the reduction R anticipates its oracle adversary to be deterministic, whenever either of the following conditions hold: (1) the adversary needs to win the security game of Q only with non-negligible probability (e.g., Q is collision-resistant hashing) or (2) that either of P and Q have “falsifiable” security games (this is the case when P is OWFs). Our work leaves open answering our main question when Q implies OWFs through a non-black-box security reduction, or when P uses a more complicated security game than a two-message one.
References
[AB09]
Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press 2009. DOI: https://doi.org/10.1017/CBO9780511804090
[AQY22]
Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from Pseudorandom Quantum States. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 208–236, Cham. 2022. Springer Nature Switzerland. DOI: https://doi.org/10.48550/arXiv.2112.10020
[ARU14]
Andris Ambainis, Ansis Rosmanis, and Dominique Unruh. Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 474–483, USA. 2014. IEEE Computer Society. DOI: 10.1109/FOCS.2014.57
[Bar01]
Boaz Barak. How to go beyond the black-box simulation barrier. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 106–115. 2001. IEEE. DOI: https://doi.org/10.1109/SFCS.2001.959885
[BB84]
Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, December 1984. DOI: https://doi.org/10.48550/arXiv.2003.06557
[BBF13]
Paul Baecher, Christina Brzuska, and Marc Fischlin. Notions of black-box reductions, revisited. In Advances in Cryptology-ASIACRYPT 2013: 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I 19, pages 296–315. 2013. Springer. DOI: https://doi.org/10.1007/978-3-642-42033-7_16
[BBK22]
Nir Bitansky, Zvika Brakerski, and Yael Tauman Kalai. Constructive Post-Quantum Reductions. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 654–683, Cham. 2022. Springer Nature Switzerland. DOI: https://doi.org/10.48550/arXiv.2203.02314
[BCM+21]
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. J. ACM, 68(5), August 2021. DOI: 10.1145/3441309
[BCQ23]
Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:21, Dagstuhl, Germany. 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.ITCS.2023.24
[BJY97]
Mihir Bellare, Markus Jakobsson, and Moti Yung. Round-optimal zero-knowledge arguments based on any one-way function. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 280–305. 1997. Springer. DOI: https://doi.org/10.1007/3-540-69053-0_20
[BZ13]
Dan Boneh and Mark Zhandry. Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 361–379. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40084-1_21
[CFP22]
Benjamin Chan, Cody Freitag, and Rafael Pass. Universal Reductions: Reductions Relative to Stateful Oracles. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography, pages 151–180, Cham. 2022. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-22368-6_6
[CLMP12]
Kai-Min Chung, Edward Lui, Mohammad Mahmoody, and Rafael Pass. Unprovable Security of 2-Message Zero Knowledge. Cryptology ePrint Archive, Paper 2012/711. 2012.
[CLMP13]
Kai-Min Chung, Huijia Lin, Mohammad Mahmoody, and Rafael Pass. On the power of nonuniformity in proofs of security. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 389–400. 2013. DOI: 10.1145/2422436.2422480
[FFS87]
Uriel Fiege, Amos Fiat, and Adi Shamir. Zero knowledge proofs of identity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 210–217. 1987. DOI: 10.1145/28395.28419
[Gol06]
Oded Goldreich. Foundations of Cryptography: Volume 1. Cambridge University Press, USA 2006. DOI: https://doi.org/10.1017/CBO9780511546891
[GW11]
Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 99–108, New York, NY, USA. 2011. Association for Computing Machinery. DOI: 10.1145/1993636.1993651
[HILL99]
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. DOI: 10.1137/S0097539793244708
[Hoe63]
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, March 1963. DOI: 10.1080/01621459.1963.10500830
[HY20]
Akinori Hosoyamada and Takashi Yamakawa. Finding Collisions in a Quantum World: Quantum Black-Box Separation of Collision-Resistance and One-Wayness. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, pages 3–32, Cham. 2020. Springer International Publishing. DOI: 10.1007/s00145-024-09517-2
[IL89]
R. Impagliazzo and M. Luby. One-way functions are essential for complexity based cryptography. In 30th Annual Symposium on Foundations of Computer Science, pages 230-235. 1989. DOI: 10.1109/SFCS.1989.63483
[ILL89]
R. Impagliazzo, L. A. Levin, and M. Luby. Pseudo-random generation from one-way functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pages 12–24, New York, NY, USA. 1989. Association for Computing Machinery. DOI: 10.1145/73007.73009
[Imp95]
R. Impagliazzo. A personal view of average-case complexity. In Proceedings of the 10th Annual Structure in Complexity Theory Conference (SCT'95), pages 134-147, USA. 1995. IEEE Computer Society. DOI: 10.1109/SCT.1995.514853
[IMS12]
Yuval Ishai, Mohammad Mahmoody, and Amit Sahai. On efficient zero-knowledge PCPs. In Theory of Cryptography: 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings 9, pages 151–168. 2012. Springer. DOI: https://doi.org/10.1007/978-3-642-28914-9_9
[IR90]
Russell Impagliazzo and Steven Rudich. Limits on the Provable Consequences of One-way Permutations. In Shafi Goldwasser, editor, Advances in Cryptology — CRYPTO' 88, pages 8–26, New York, NY. 1990. Springer New York. DOI: 10.1145/73007.73012
[JLS18]
Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom Quantum States. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 126–152, Cham. 2018. Springer International Publishing. DOI: https://doi.org/10.1007/978-3-319-96878-0_5
[KQST23]
William Kretschmer, Luowen Qian, Makrand Sinha, and Avishay Tal. Quantum Cryptography in Algorithmica. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1589–1602, New York, NY, USA. 2023. Association for Computing Machinery. DOI: 10.1145/3564246.3585225
[Kre21]
William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In Min-Hsiu Hsieh, editor, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), volume 197 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:20, Dagstuhl, Germany. 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.TQC.2021.2
[LM22]
Alex Lombardi and Fermi Ma. Quantum Rewinding Tutorial, Part 1: Motivation and Early Rewinding Techniques. In Quantum and Lattices Joint Reunion Workshop, Simons Institute, Berekly. 2022.
[LMQW22]
Alex Lombardi, Ethan Mook, Willy Quach, and Daniel Wichs. Post-quantum Insecurity from LWE. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography, pages 3–32, Cham. 2022. Springer Nature Switzerland. DOI: 10.1007/978-3-031-22318-1_1
[MY22]
Tomoyuki Morimae and Takashi Yamakawa. Quantum Commitments and Signatures Without One-Way Functions. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, pages 269–295, Cham. 2022. Springer Nature Switzerland. DOI: 10.1007/978-3-031-15802-5_10
[Nao03]
Moni Naor. On Cryptographic Assumptions and Challenges. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, pages 96–109, Berlin, Heidelberg. 2003. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-540-45146-4_6
[NY89]
Moni Naor and Moti Yung. Universal One-Way Hash Functions and their Cryptographic Applications. In 21st ACM STOC, pages 33–43. May 1989. ACM Press. DOI: 10.1145/73007.73011
[Pas11]
Rafael Pass. Limits of provable security from standard assumptions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 109–118. 2011. DOI: 10.1145/1993636.1993652
[Rom90]
J. Rompel. One-way functions are necessary and sufficient for secure signatures. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pages 387–394, New York, NY, USA. 1990. Association for Computing Machinery. DOI: 10.1145/100216.100269
[RTV04]
Omer Reingold, Luca Trevisan, and Salil Vadhan. Notions of Reducibility between Cryptographic Primitives. In Moni Naor, editor, Theory of Cryptography, pages 1–20, Berlin, Heidelberg. 2004. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-540-24638-1_1
[Sha20]
Ronen Shaltiel. Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. DOI: https://doi.org/10.1007/s00037-023-00238-9
[Sho94]
P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124-134. 1994. DOI: 10.1109/SFCS.1994.365700
[Son14]
Fang Song. A Note on Quantum Security for Post-Quantum Cryptography. In Michele Mosca, editor, Post-Quantum Cryptography, pages 246–265, Cham. 2014. Springer International Publishing. DOI: https://doi.org/10.48550/arXiv.1409.2187
[Unr12]
Dominique Unruh. Quantum Proofs of Knowledge. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 135–152, Berlin, Heidelberg. 2012. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-642-29011-4_10
[Wat06]
John Watrous. Zero-knowledge against quantum attacks. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pages 296–305, New York, NY, USA. 2006. Association for Computing Machinery. DOI: 10.1145/1132516.1132560
[Wat08]
John Watrous. Quantum Computational Complexity. 2008.
[Wic13]
Daniel Wichs. Barriers in cryptography with weak, correlated and leaky sources. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pages 111–126, New York, NY, USA. 2013. Association for Computing Machinery. DOI: 10.1145/2422436.2422451
[WZ82]
W. K. Wootters and W. H. Zurek. A single quantum cannot be cloned. Nature, 299(5886):802-803, October 1982. DOI: 10.1038/299802a0
[YZ20]
Takashi Yamakawa and Mark Zhandry. A note on separating classical and quantum random oracles. Cryptology ePrint Archive, 2020.
PDF
History
Submitted: 2024-10-09
Accepted: 2024-12-03
Published: 2025-01-13
Accepted: 2024-12-03
Published: 2025-01-13
How to cite
Sam Buxbaum and Mohammad Mahmoody, A Note on the Minimality of One-Way Functions in Post-Quantum Cryptography. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/a6ksr-10k.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.