On the Computational Hardness of Quantum One-Wayness
1Department of Computer Science, University of Oxford, Oxford, UK
2Department of Computer Science, New York University, New York, USA
3Department of Computer Science, Cornell Tech, USA
4Department of Computer Science, UC Berkeley, USA
| Published: | 2025-03-27, volume 9, page 1679 |
| Editor: | Tomoyuki Morimae |
| Eprint: | arXiv:2312.08363v4 |
| Doi: | https://doi.org/10.22331/q-2025-03-27-1679 |
| Citation: | Quantum 9, 1679 (2025). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that $\rm{P} \neq \rm{NP}$, which gives a lower bound on the necessary hardness.
One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.
We show that pseudorandom states compressing $n$ bits to $\log n + 1$ qubits can be used to build one-way state generators and pseudorandom states compressing $n$ bits to $\omega(\log n)$ qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than $c \log n$-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a $\rm{PP}$ oracle.
An interesting implication of our results is that a $t(n)$-copy one-way state generator exists unconditionally, for every $t(n) = o(n/\log n)$. This contrasts nicely with the previously known fact that $O(n)$-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments.
► BibTeX data
► References
[1] Mihir Bellare, Lenore Cowen, and Shafi Goldwasser. ``On the structure of secret key exchange protocols''. In Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings. Volume 435 of Lecture Notes in Computer Science, pages 604–605. Springer (1989).
https://doi.org/10.1007/0-387-34805-0_53
[2] R. Impagliazzo and S. Rudich. ``Limits on the provable consequences of one-way permutations''. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing. Page 44–61. STOC '89New York, NY, USA (1989). Association for Computing Machinery.
https://doi.org/10.1145/73007.73012
[3] R. Impagliazzo. ``A personal view of average-case complexity''. In Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference. Pages 134–147. (1995).
https://doi.org/10.1109/SCT.1995.514853
[4] Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''. Theoretical Computer Science 560, 7–11 (2014).
https://doi.org/10.1016/j.tcs.2014.05.025
[5] Stephen Wiesner. ``Conjugate coding''. SIGACT News 15, 78–88 (1983).
https://doi.org/10.1145/1008908.1008920
[6] Hoi-Kwong Lo and H. F. Chau. ``Is quantum bit commitment really possible?''. Physical Review Letters 78, 3410–3413 (1997).
https://doi.org/10.1103/physrevlett.78.3410
[7] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. ``Pseudorandom quantum states''. In Advances in Cryptology–CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III 38. Pages 126–152. Springer (2018).
https://doi.org/10.1007/978-3-319-96878-0_5
[8] Dakshita Khurana and Kabir Tomer. ``Commitments from quantum one-wayness''. CoRR abs/2310.11526 (2023). arXiv:2310.11526.
https://doi.org/10.48550/ARXIV.2310.11526
arXiv:2310.11526
[9] 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, July 5-8, 2021, Virtual Conference. Volume 197 of LIPIcs, pages 2:1–2:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021).
https://doi.org/10.4230/LIPICS.TQC.2021.2
[10] 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 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part I. Volume 13507 of Lecture Notes in Computer Science, pages 269–295. Springer (2022).
https://doi.org/10.1007/978-3-031-15802-5_10
[11] Prabhanjan Ananth, Aditya Gulati, Luowen Qian, and Henry Yuen. ``Pseudorandom (function-like) quantum state generators: New definitions and applications''. In Eike Kiltz and Vinod Vaikuntanathan, editors, Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part I. Volume 13747 of Lecture Notes in Computer Science, pages 237–265. Springer (2022).
https://doi.org/10.1007/978-3-031-22318-1_9
[12] Zvika Brakerski and Omri Shmueli. ``Scalable pseudorandom quantum states'' (2020). arXiv:2004.01976.
arXiv:2004.01976
[13] Tomoyuki Morimae and Takashi Yamakawa. ``One-wayness in quantum cryptography''. In Frédéric Magniez and Alex Bredariol Grilo, editors, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024, September 9-13, 2024, Okinawa, Japan. Volume 310 of LIPIcs, pages 4:1–4:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024).
https://doi.org/10.4230/LIPICS.TQC.2024.4
[14] 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, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA. Volume 251 of LIPIcs, pages 24:1–24:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023).
https://doi.org/10.4230/LIPICS.ITCS.2023.24
[15] Daniel Gottesman and Isaac Chuang. ``Quantum digital signatures'' (2001). arXiv:quant-ph/0105032.
arXiv:quant-ph/0105032
[16] Alex Lombardi, Fermi Ma, and John Wright. ``A one-query lower bound for unitary synthesis and breaking quantum cryptography''. Cryptology ePrint Archive, Paper 2023/1602 (2023). https://eprint.iacr.org/2023/1602.
https://eprint.iacr.org/2023/1602
[17] Jun Yan. ``General properties of quantum bit commitments (extended abstract)''. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part IV. Volume 13794 of Lecture Notes in Computer Science, pages 628–657. Springer (2022).
https://doi.org/10.1007/978-3-031-22972-5_22
[18] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. ``Exact and approximate unitary 2-designs and their application to fidelity estimation''. Physical Review A 80, 012304 (2009).
https://doi.org/10.1103/PhysRevA.80.012304
[19] Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth. ``Efficient unitary designs with a system-size independent number of non-clifford gates''. Communications in Mathematical Physics 397, 995–1041 (2023).
https://doi.org/10.1007/s00220-022-04507-6
[20] Ryan O'Donnell, Rocco A. Servedio, and Pedro Paredes. ``Explicit orthogonal and unitary designs'' (2023). arXiv:2310.13597.
arXiv:2310.13597
[21] Scott Aaronson. ``Quantum computing, postselection, and probabilistic polynomial-time''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461, 3473 – 3482 (2005). url: https://api.semanticscholar.org/CorpusID:1770389.
https://doi.org/10.1098/rspa.2005.1546
https://api.semanticscholar.org/CorpusID:1770389
[22] Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. ``Quantum search-to-decision reductions and the state synthesis problem''. In Shachar Lovett, editor, 37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA. Volume 234 of LIPIcs, pages 5:1–5:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022).
https://doi.org/10.4230/LIPICS.CCC.2022.5
[23] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa. ``A note on output length of one-way state generators''. CoRR abs/2312.16025 (2023). arXiv:2312.16025.
https://doi.org/10.48550/ARXIV.2312.16025
arXiv:2312.16025
[24] Rishabh Batra and Rahul Jain. ``Commitments are equivalent to statistically-verifiable one-way state generators''. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 1178–1192. (2024).
https://doi.org/10.1109/FOCS61266.2024.00077
[25] Dakshita Khurana and Kabir Tomer. ``Founding quantum cryptography on quantum advantage, or, towards cryptography from $\#\mathsf{P}$-hardness''. Cryptology ePrint Archive, Paper 2024/1490 (2024).
[26] Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa. ``A new world in the depths of microcrypt: Separating owsgs and quantum money from qefid'' (2025). arXiv:2410.03453.
arXiv:2410.03453
[27] John Bostanci, Boyang Chen, and Barak Nehoran. ``Oracle separation between quantum commitments and quantum one-wayness'' (2024). arXiv:2410.03358.
arXiv:2410.03358
[28] Sanjeev Arora and Boaz Barak. ``Computational complexity - A modern approach''. Cambridge University Press. (2009). url: http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264.
http://www.cambridge.org/catalogue/catalogue.asp?isbn=9780521424264
[29] Greg Kuperberg. ``How hard is it to approximate the jones polynomial?''. Theory of Computing 11, 183–219 (2015).
https://doi.org/10.4086/toc.2015.v011a006
[30] Fernando GSL Brandao, Aram W Harrow, and Michał Horodecki. ``Local random quantum circuits are approximate polynomial-designs''. Communications in Mathematical Physics 346, 397–434 (2016).
https://doi.org/10.1007/s00220-016-2706-8
[31] Patrick Hayden, Debbie W Leung, and Andreas Winter. ``Aspects of generic entanglement''. Communications in mathematical physics 265, 95–117 (2006).
https://doi.org/10.1007/s00220-006-1535-6
[32] Mervin E. Muller. ``A note on a method for generating points uniformly on n-dimensional spheres''. Commun. ACM 2, 19–20 (1959).
https://doi.org/10.1145/377939.377946
Cited by
[1] Eli Goldin and Mark Zhandry, Lecture Notes in Computer Science 16001, 269 (2025) ISBN:978-3-032-01877-9.
[2] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa, "A Note on Output Length of One-Way State Generators and EFIs", Abstract_only IACR Communications in Cryptology 2 3, cc2-3-48 (2025).
[3] YELİZ KARACA, DUMITRU BALEANU, YU-DONG ZHANG, OSVALDO GERVASI, and MAJAZ MOONIS, "EDITORIAL ARTICLE OF SPECIAL ISSUE: PART I-A SERIES — MATHEMATICAL MODELING OF COMPLEX SYSTEMS: FRACTALS-FRACTIONAL-ITÔ-DEs- WAVELET-ENTROPY-AI-BASED THEORIES, ANALYSES AND APPLICATIONS", Fractals 34 04, 2602002 (2026).
[4] James Bartusek, Dakshita Khurana, Fuyuki Kitagawa, Giulio Malavolta, Ryo Nishimaki, Alexander Poremba, Michael Walter, and Takashi Yamakawa, "Publicly Verifiable Deletion: General Compilers from Minimal Assumptions", Journal of Cryptology 39 3, 26 (2026).
[5] William Kretschmer, "Quantum Pseudorandomness and Classical Complexity", arXiv:2103.09320, (2021).
[6] Tomoyuki Morimae and Takashi Yamakawa, "One-Wayness in Quantum Cryptography", arXiv:2210.03394, (2022).
[7] Dakshita Khurana and Kabir Tomer, "Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness", arXiv:2409.15248, (2024).
[8] Prabhanjan Ananth and Eli Goldin, "Less is More: On Copy Complexity in Quantum Cryptography", arXiv:2510.04992, (2025).
[9] Tomoyuki Morimae, Shogo Yamada, and Takashi Yamakawa, "Quantum Unpredictability", arXiv:2405.04072, (2024).
[10] Bruno P. Cavalar, Eli Goldin, Matthew Gray, and Peter Hall, "A Meta-Complexity Characterization of Quantum Cryptography", arXiv:2410.04984, (2024).
[11] Minki Hhan, Tomoyuki Morimae, and Takashi Yamakawa, "A Note on Output Length of One-Way State Generators and EFIs", arXiv:2312.16025, (2023).
[12] Taiga Hiroka and Min-Hsiu Hsieh, "Computational Complexity of Learning Efficiently Generatable Pure States", arXiv:2410.04373, (2024).
[13] Kai-Min Chung, Eli Goldin, and Matthew Gray, "On Central Primitives for Quantum Cryptography with Classical Communication", arXiv:2402.17715, (2024).
[14] Eli Goldin, Tomoyuki Morimae, Saachi Mutreja, and Takashi Yamakawa, "CountCrypt: Quantum Cryptography between QCMA and PP", arXiv:2410.14792, (2024).
[15] Amit Behera, Giulio Malavolta, Tomoyuki Morimae, Tamer Mour, and Takashi Yamakawa, "A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID", arXiv:2410.03453, (2024).
The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 16:59:24) and SAO/NASA ADS (last updated successfully 2026-07-15 16:59:25). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.