A Note on Quantum-Secure PRPs

Mark Zhandry

doi:10.22331/q-2025-04-08-1696

A Note on Quantum-Secure PRPs

Mark Zhandry

NTT Research

Published:	2025-04-08, volume 9, page 1696
Editor:	Tomoyuki Morimae
Eprint:	arXiv:1611.05564v3
Doi:	https://doi.org/10.22331/q-2025-04-08-1696
Citation:	Quantum 9, 1696 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We show how to construct pseudorandom permutations (PRPs) that remain secure even if the adversary can query the permutation, both in the forward and reverse directions, on a quantum superposition of inputs. Such quantum-secure PRPs have found numerous applications in cryptography and complexity theory. Our construction combines a quantum-secure pseudorandom function together with constructions of classical format preserving encryption. By combining known results, we show how to construct quantum-secure PRP in this model whose security relies only on the existence of one-way functions.

► BibTeX data

@article{Zhandry2025notequantumsecure,
  doi = {10.22331/q-2025-04-08-1696},
  url = {https://doi.org/10.22331/q-2025-04-08-1696},
  title = {A {N}ote on {Q}uantum-{S}ecure {PRP}s},
  author = {Zhandry, Mark},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1696},
  month = apr,
  year = {2025}
}

► References

[1] Scott Aaronson. Quantum Copy-Protection and Quantum Money. Proceedings of the 24th Annual IEEE Conference on Computaitonal Complexity (CCC), 2009. https://doi.org/10.1109/CCC.2009.42.
https://doi.org/10.1109/CCC.2009.42

[2] Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, and Zixin Zhou. Quantum pseudoentanglement. In Venkatesan Guruswami, editor, ITCS 2024: 15th Innovations in Theoretical Computer Science Conference, volume 287, pages 2:1–2:21, Berkeley, CA, USA, January 30 – February 2, 2024. Leibniz International Proceedings in Informatics (LIPIcs). https://doi.org/10.4230/LIPIcs.ITCS.2024.2.
https://doi.org/10.4230/LIPIcs.ITCS.2024.2

[3] Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Howard J. Karloff and Toniann Pitassi, editors, 44th Annual ACM Symposium on Theory of Computing, pages 41–60, New York, NY, USA, May 19–22, 2012. ACM Press. https://doi.org/10.1145/2213977.2213983.
https://doi.org/10.1145/2213977.2213983

[4] Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32nd Computational Complexity Conference, CCC '17, Dagstuhl, DEU, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.CCC.2017.22.
https://doi.org/10.4230/LIPIcs.CCC.2017.22

[5] Rotem Arnon-Friedman, Zvika Brakerski, and Thomas Vidick. Computational entanglement theory, 2023. https://arxiv.org/abs/2310.02783.
arXiv:2310.02783

[6] Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. Pseudorandom isometries. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part IV, volume 14654 of Lecture Notes in Computer Science, pages 226–254, Zurich, Switzerland, May 26–30, 2024. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-031-58737-5_9.
https://doi.org/10.1007/978-3-031-58737-5_9

[7] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-access-secure message authentication via blind-unforgeability. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part III, volume 12107 of Lecture Notes in Computer Science, pages 788–817, Zagreb, Croatia, May 10–14, 2020. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-030-45727-3_27.
https://doi.org/10.1007/978-3-030-45727-3_27

[8] Amit Behera, Zvika Brakerski, Or Sattath, and Omri Shmueli. Pseudorandomness with proof of destruction and applications. In Guy N. Rothblum and Hoeteck Wee, editors, TCC 2023: 21st Theory of Cryptography Conference, Part IV, volume 14372 of Lecture Notes in Computer Science, pages 125–154, Taipei, Taiwan, November 29 – December 2, 2023. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-031-48624-1_5.
https://doi.org/10.1007/978-3-031-48624-1_5

[9] Ritam Bhaumik, Benoı̂t Cogliati, Jordan Ethan, and Ashwin Jha. Mind the bad norms: Revisiting compressed oracle-based quantum indistinguishability proofs. In Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part IX, page 215–247, Berlin, Heidelberg, 2024. Springer-Verlag. https://doi.org/10.1007/978-981-96-0947-5_8.
https://doi.org/10.1007/978-981-96-0947-5_8

[10] Joppe W. Bos, Andreas Hülsing, Joost Renes, and Christine van Vredendaal. Rapidly verifiable XMSS signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(1):137–168, 2021. https://doi.org/10.46586/tches.v2021.i1.137-168.
https://doi.org/10.46586/tches.v2021.i1.137-168

[11] Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low T-gate complexity. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part II, volume 9216 of Lecture Notes in Computer Science, pages 609–629, Santa Barbara, CA, USA, August 16–20, 2015. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-662-48000-7_30.
https://doi.org/10.1007/978-3-662-48000-7_30

[12] Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers. Format-preserving encryption. In Michael J. Jacobson, Jr., Vincent Rijmen, and Reihaneh Safavi-Naini, editors, SAC 2009: 16th Annual International Workshop on Selected Areas in Cryptography, volume 5867 of Lecture Notes in Computer Science, pages 295–312, Calgary, Alberta, Canada, August 13–14, 2009. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-642-05445-7_19.
https://doi.org/10.1007/978-3-642-05445-7_19

[13] Dan Boneh and Mark Zhandry. Quantum-secure message authentication codes. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 592–608, Athens, Greece, May 26–30, 2013. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-642-38348-9_35.
https://doi.org/10.1007/978-3-642-38348-9_35

[14] Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science, pages 361–379, Santa Barbara, CA, USA, August 18–22, 2013. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-642-40084-1_21.
https://doi.org/10.1007/978-3-642-40084-1_21

[15] Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth, 2022. https://arxiv.org/abs/2205.04656.
arXiv:2205.04656

[16] Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, and Louis Salvail. Superposition attacks on cryptographic protocols. In Carles Padró, editor, ICITS 13: 7th International Conference on Information Theoretic Security, volume 8317 of Lecture Notes in Computer Science, pages 142–161, Singapore, 2014. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-319-04268-8_9.
https://doi.org/10.1007/978-3-319-04268-8_9

[17] Ehsan Ebrahimi, Céline Chevalier, Marc Kaplan, and Michele Minelli. Superposition attack on OT protocols. Cryptology ePrint Archive, Report 2020/798, 2020. https://eprint.iacr.org/2020/798.
https://eprint.iacr.org/2020/798

[18] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792–807, October 1986. https://doi.org/10.1145/6490.6503.
https://doi.org/10.1145/6490.6503

[19] Tommaso Gagliardoni, Andreas Hülsing, and Christian Schaffner. Semantic security and indistinguishability in the quantum world. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part III, volume 9816 of Lecture Notes in Computer Science, pages 60–89, Santa Barbara, CA, USA, August 14–18, 2016. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-662-53015-3_3.
https://doi.org/10.1007/978-3-662-53015-3_3

[20] Louis Granboulan and Thomas Pornin. Perfect block ciphers with small blocks. In Alex Biryukov, editor, Fast Software Encryption – FSE 2007, volume 4593 of Lecture Notes in Computer Science, pages 452–465, Luxembourg, Luxembourg, March 26–28, 2007. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-540-74619-5_28.
https://doi.org/10.1007/978-3-540-74619-5_28

[21] Tudor Giurgica-Tiron and Adam Bouland. Pseudorandomness from subset states, 2023. https://arxiv.org/abs/2312.09206.
arXiv:2312.09206

[22] Sumegha Garg, Henry Yuen, and Mark Zhandry. New security notions and feasibility results for authentication of quantum data. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part II, volume 10402 of Lecture Notes in Computer Science, pages 342–371, Santa Barbara, CA, USA, August 20–24, 2017. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-319-63715-0_12.
https://doi.org/10.1007/978-3-319-63715-0_12

[23] Akinori Hosoyamada and Tetsu Iwata. 4-round Luby-Rackoff construction is a qPRP. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology – ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, pages 145–174, Kobe, Japan, December 8–12, 2019. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-030-34578-5_6.
https://doi.org/10.1007/978-3-030-34578-5_6

[24] 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. https://doi.org/10.1137/S0097539793244708.
https://doi.org/10.1137/S0097539793244708

[25] Viet Tung Hoang, Ben Morris, and Phillip Rogaway. An enciphering scheme based on a card shuffle. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 1–13, Santa Barbara, CA, USA, August 19–23, 2012. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-642-32009-5_1.
https://doi.org/10.1007/978-3-642-32009-5_1

[26] Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Breaking symmetric cryptosystems using quantum period finding. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 207–237, Santa Barbara, CA, USA, August 14–18, 2016. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-662-53008-5_8.
https://doi.org/10.1007/978-3-662-53008-5_8

[27] Hidenori Kuwakado and Masakatu Morii. Quantum distinguisher between the 3-round feistel cipher and the random permutation. In 2010 IEEE International Symposium on Information Theory, pages 2682–2685, 2010. https://doi.org/10.1109/ISIT.2010.5513654.
https://doi.org/10.1109/ISIT.2010.5513654

[28] Chuhan Lu, Minglong Qin, Fang Song, Penghui Yao, and Mingnan Zhao. Quantum pseudorandom scramblers. In Elette Boyle and Mohammad Mahmoody, editors, Theory of Cryptography: 22nd International Conference, TCC 2024, Milan, Italy, December 2–6, 2024, Proceedings, Part II, pages 3–35, Cham, 2025. Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-78017-2_1.
https://doi.org/10.1007/978-3-031-78017-2_1

[29] Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), 1988. https://doi.org/10.1137/0217022.
https://doi.org/10.1137/0217022

[30] Qipeng Liu, Amit Sahai, and Mark Zhandry. Quantum immune one-time memories. Cryptology ePrint Archive, Report 2020/871, 2020. https://eprint.iacr.org/2020/871.
https://eprint.iacr.org/2020/871

[31] Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In STOC 2025 (to appear), 2025. https://arxiv.org/abs/2410.10116.
arXiv:2410.10116

[32] Ben Morris. The mixing time of the Thorp shuffle. In Harold N. Gabow and Ronald Fagin, editors, 37th Annual ACM Symposium on Theory of Computing, pages 403–412, Baltimore, MA, USA, May 22–24, 2005. ACM Press. https://doi.org/10.1145/1060590.1060651.
https://doi.org/10.1145/1060590.1060651

[33] Ben Morris and Phillip Rogaway. Sometimes-recurse shuffle - almost-random permutations in logarithmic expected time. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 311–326, Copenhagen, Denmark, May 11–15, 2014. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-642-55220-5_18.
https://doi.org/10.1007/978-3-642-55220-5_18

[34] Thomas Ristenpart and Scott Yilek. The mix-and-cut shuffle: Small-domain encryption secure against N queries. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 392–409, Santa Barbara, CA, USA, August 18–22, 2013. Springer Berlin Heidelberg, Germany. https://doi.org/10.1007/978-3-642-40041-4_22.
https://doi.org/10.1007/978-3-642-40041-4_22

[35] Fang Song. Quantum-secure pseudorandom permutations, 2017. Blog post: https://qcc.fangsong.info/2017-06-quantumprp.
https://qcc.fangsong.info/2017-06-quantumprp

[36] Emil Stefanov and Elaine Shi. FastPRP: Fast pseudo-random permutations for small domains. Cryptology ePrint Archive, Report 2012/254, 2012. https://eprint.iacr.org/2012/254.
https://eprint.iacr.org/2012/254

[37] Mark Zhandry. How to construct quantum random functions. In 53rd Annual Symposium on Foundations of Computer Science, pages 679–687, New Brunswick, NJ, USA, October 20–23, 2012. IEEE Computer Society Press. https://doi.org/10.1109/FOCS.2012.37.
https://doi.org/10.1109/FOCS.2012.37

[38] Mark Zhandry. Redeeming reset indifferentiability and applications to post-quantum security. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part I, volume 13090 of Lecture Notes in Computer Science, pages 518–548, Singapore, December 6–10, 2021. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-030-92062-3_18.
https://doi.org/10.1007/978-3-030-92062-3_18

Cited by

[1] Leonardo Lavagna, Francesca De Falco, Andrea Ceschini, Antonello Rosato, and Massimo Panella, 2025 IEEE International Symposium on Circuits and Systems (ISCAS) 1 (2025) ISBN:979-8-3503-5683-0.

[2] Xiaozhou Feng, Zihan Cheng, and Matteo Ippoliti, "Hardness of Observing Strong-to-Weak Symmetry Breaking", Physical Review Letters 135 20, 200402 (2025).

[3] Scott Aaronson and Lijie Chen, "Complexity-Theoretic Foundations of Quantum Supremacy Experiments", arXiv:1612.05903, (2016).

[4] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang, "Random unitaries in extremely low depth", arXiv:2407.07754, (2024).

[5] Fermi Ma and Hsin-Yuan Huang, "How to Construct Random Unitaries", arXiv:2410.10116, (2024).

[6] Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang, "Random unitaries in extremely low depth", Science 389 6755, 92 (2025).

[7] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen, "Simple constructions of linear-depth t-designs and pseudorandom unitaries", arXiv:2404.12647, (2024).

[8] Laura Cui, Thomas Schuster, Fernando Brandao, and Hsin-Yuan Huang, "Unitary designs in nearly optimal depth", arXiv:2507.06216, (2025).

[9] Fernando Granha Jeronimo, Nir Magrafta, and Pei Wu, "Pseudorandom and Pseudoentangled States from Subset States", arXiv:2312.15285, (2023).

[10] Xiaozhou Feng and Matteo Ippoliti, "Dynamics of pseudoentanglement", Journal of High Energy Physics 2025 2, 128 (2025).

[11] Rotem Arnon, Zvika Brakerski, and Thomas Vidick, "Computational Entanglement Theory", arXiv:2310.02783, (2023).

[12] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen, "Pseudorandom unitaries with non-adaptive security", arXiv:2402.14803, (2024).

[13] Thomas Schuster, Fermi Ma, Alex Lombardi, Fernando Brandao, and Hsin-Yuan Huang, "Strong random unitaries and fast scrambling", arXiv:2509.26310, (2025).

[14] Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin, "Pseudorandom Isometries", arXiv:2311.02901, (2023).

[15] Nai-Hui Chia and Shih-Han Hung, "Classical verification of quantum depth", arXiv:2205.04656, (2022).

[16] Prabhanjan Ananth, Saachi Mutreja, and Alexander Poremba, "Revocable Encryption, Programs, and More: The Case of Multi-Copy Security", arXiv:2410.13163, (2024).

[17] Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen, "Random Unitaries in Constant (Quantum) Time", arXiv:2508.11487, (2025).

[18] Dmitry Grinko and Satoshi Yoshida, "Quantum Simulation of Random Unitaries from Clebsch-Gordan Transforms", arXiv:2509.26623, (2025).

[19] Wonjun Lee, Hyukjoon Kwon, and Gil Young Cho, "Fast pseudothermalization", arXiv:2411.03974, (2024).

[20] Thomas Schuster, Dominik Kufel, Norman Y. Yao, and Hsin-Yuan Huang, "Hardness of recognizing phases of matter", arXiv:2510.08503, (2025).

[21] Nai-Hui Chia, Daniel Liang, and Fang Song, "Quantum State Learning Implies Circuit Lower Bounds", arXiv:2405.10242, (2024).

[22] Gorjan Alagic, Stacey Jeffery, Maris Ozols, and Alexander Poremba, "On Quantum Chosen-Ciphertext Attacks and Learning with Errors", arXiv:1808.09655, (2018).

[23] Zvika Brakerski and Nir Magrafta, "Real-Valued Somewhat-Pseudorandom Unitaries", arXiv:2403.16704, (2024).

[24] Omri Shmueli and Mark Zhandry, "On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations", arXiv:2507.12456, (2025).

[25] Tommaso Gagliardoni, "Quantum Security of Cryptographic Primitives", arXiv:1705.02417, (2017).

[26] Hector Bjoljahn Hougaard, "How to Generate Pseudorandom Permutations Over Other Groups: Even-Mansour and Feistel Revisited", arXiv:1707.01699, (2017).

[27] Gorjan Alagic, Joseph Carolan, Christian Majenz, and Saliha Tokat, "The Sponge is Quantum Indifferentiable", arXiv:2504.16887, (2025).

[28] Hector Bjoljahn Hougaard, "How to Generate Pseudorandom Permutations Over Other Groups", arXiv:1710.05645, (2017).

[29] Luowen Qian and Mark Zhandry, "Impersonating Quantum Secrets over Classical Channels", arXiv:2601.01058, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 03:00:14) and SAO/NASA ADS (last updated successfully 2026-08-09 03:00:15). 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.