{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T21:15:06Z","timestamp":1762982106163,"version":"3.40.3"},"reference-count":38,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T00:00:00Z","timestamp":1744070400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.22331\/q-2025-04-08-1696","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T13:09:44Z","timestamp":1744117784000},"page":"1696","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["A Note on Quantum-Secure PRPs"],"prefix":"10.22331","volume":"9","author":[{"given":"Mark","family":"Zhandry","sequence":"first","affiliation":[{"name":"NTT Research"}]}],"member":"9598","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/CCC.2009.42"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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\u20132:21, Berkeley, CA, USA, January 30 \u2013 February 2, 2024. Leibniz International Proceedings in Informatics (LIPIcs). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2024.2.","DOI":"10.4230\/LIPIcs.ITCS.2024.2"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u201360, New York, NY, USA, May 19\u201322, 2012. ACM Press. https:\/\/doi.org\/10.1145\/2213977.2213983.","DOI":"10.1145\/2213977.2213983"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In Proceedings of the 32nd Computational Complexity Conference, CCC &apos;17, Dagstuhl, DEU, 2017. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.22.","DOI":"10.4230\/LIPIcs.CCC.2017.22"},{"key":"4","unstructured":"Rotem Arnon-Friedman, Zvika Brakerski, and Thomas Vidick. Computational entanglement theory, 2023. https:\/\/arxiv.org\/abs\/2310.02783."},{"key":"5","doi-asserted-by":"publisher","unstructured":"Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, and Yao-Ting Lin. Pseudorandom isometries. In Marc Joye and Gregor Leander, editors, Advances in Cryptology \u2013 EUROCRYPT 2024, Part IV, volume 14654 of Lecture Notes in Computer Science, pages 226\u2013254, Zurich, Switzerland, May 26\u201330, 2024. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-031-58737-5_9.","DOI":"10.1007\/978-3-031-58737-5_9"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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 \u2013 EUROCRYPT 2020, Part III, volume 12107 of Lecture Notes in Computer Science, pages 788\u2013817, Zagreb, Croatia, May 10\u201314, 2020. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-030-45727-3_27.","DOI":"10.1007\/978-3-030-45727-3_27"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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\u2013154, Taipei, Taiwan, November 29 \u2013 December 2, 2023. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-031-48624-1_5.","DOI":"10.1007\/978-3-031-48624-1_5"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Ritam Bhaumik, Beno\u0131\u0302t Cogliati, Jordan Ethan, and Ashwin Jha. Mind the bad norms: Revisiting compressed oracle-based quantum indistinguishability proofs. In Advances in Cryptology \u2013 ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9\u201313, 2024, Proceedings, Part IX, page 215\u2013247, Berlin, Heidelberg, 2024. Springer-Verlag. https:\/\/doi.org\/10.1007\/978-981-96-0947-5_8.","DOI":"10.1007\/978-981-96-0947-5_8"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Joppe W. Bos, Andreas H\u00fclsing, Joost Renes, and Christine van Vredendaal. Rapidly verifiable XMSS signatures. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(1):137\u2013168, 2021. https:\/\/doi.org\/10.46586\/tches.v2021.i1.137-168.","DOI":"10.46586\/tches.v2021.i1.137-168"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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 \u2013 CRYPTO 2015, Part II, volume 9216 of Lecture Notes in Computer Science, pages 609\u2013629, Santa Barbara, CA, USA, August 16\u201320, 2015. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-662-48000-7_30.","DOI":"10.1007\/978-3-662-48000-7_30"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u2013312, Calgary, Alberta, Canada, August 13\u201314, 2009. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-642-05445-7_19.","DOI":"10.1007\/978-3-642-05445-7_19"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Dan Boneh and Mark Zhandry. Quantum-secure message authentication codes. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology \u2013 EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 592\u2013608, Athens, Greece, May 26\u201330, 2013. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-642-38348-9_35.","DOI":"10.1007\/978-3-642-38348-9_35"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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 \u2013 CRYPTO 2013, Part II, volume 8043 of Lecture Notes in Computer Science, pages 361\u2013379, Santa Barbara, CA, USA, August 18\u201322, 2013. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-642-40084-1_21.","DOI":"10.1007\/978-3-642-40084-1_21"},{"key":"14","unstructured":"Nai-Hui Chia and Shih-Han Hung. Classical verification of quantum depth, 2022. https:\/\/arxiv.org\/abs\/2205.04656."},{"key":"15","doi-asserted-by":"publisher","unstructured":"Ivan Damg\u00e5rd, Jakob Funder, Jesper Buus Nielsen, and Louis Salvail. Superposition attacks on cryptographic protocols. In Carles Padr\u00f3, editor, ICITS 13: 7th International Conference on Information Theoretic Security, volume 8317 of Lecture Notes in Computer Science, pages 142\u2013161, Singapore, 2014. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-319-04268-8_9.","DOI":"10.1007\/978-3-319-04268-8_9"},{"key":"16","unstructured":"Ehsan Ebrahimi, C\u00e9line Chevalier, Marc Kaplan, and Michele Minelli. Superposition attack on OT protocols. Cryptology ePrint Archive, Report 2020\/798, 2020. https:\/\/eprint.iacr.org\/2020\/798."},{"key":"17","doi-asserted-by":"publisher","unstructured":"Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM, 33(4):792\u2013807, October 1986. https:\/\/doi.org\/10.1145\/6490.6503.","DOI":"10.1145\/6490.6503"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Tommaso Gagliardoni, Andreas H\u00fclsing, and Christian Schaffner. Semantic security and indistinguishability in the quantum world. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology \u2013 CRYPTO 2016, Part III, volume 9816 of Lecture Notes in Computer Science, pages 60\u201389, Santa Barbara, CA, USA, August 14\u201318, 2016. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-662-53015-3_3.","DOI":"10.1007\/978-3-662-53015-3_3"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Louis Granboulan and Thomas Pornin. Perfect block ciphers with small blocks. In Alex Biryukov, editor, Fast Software Encryption \u2013 FSE 2007, volume 4593 of Lecture Notes in Computer Science, pages 452\u2013465, Luxembourg, Luxembourg, March 26\u201328, 2007. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-540-74619-5_28.","DOI":"10.1007\/978-3-540-74619-5_28"},{"key":"20","unstructured":"Tudor Giurgica-Tiron and Adam Bouland. Pseudorandomness from subset states, 2023. https:\/\/arxiv.org\/abs\/2312.09206."},{"key":"21","doi-asserted-by":"publisher","unstructured":"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 \u2013 CRYPTO 2017, Part II, volume 10402 of Lecture Notes in Computer Science, pages 342\u2013371, Santa Barbara, CA, USA, August 20\u201324, 2017. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-319-63715-0_12.","DOI":"10.1007\/978-3-319-63715-0_12"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Akinori Hosoyamada and Tetsu Iwata. 4-round Luby-Rackoff construction is a qPRP. In Steven D. Galbraith and Shiho Moriai, editors, Advances in Cryptology \u2013 ASIACRYPT 2019, Part I, volume 11921 of Lecture Notes in Computer Science, pages 145\u2013174, Kobe, Japan, December 8\u201312, 2019. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-030-34578-5_6.","DOI":"10.1007\/978-3-030-34578-5_6"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Johan H\u00e5stad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364\u20131396, 1999. https:\/\/doi.org\/10.1137\/S0097539793244708.","DOI":"10.1137\/S0097539793244708"},{"key":"24","doi-asserted-by":"publisher","unstructured":"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 \u2013 CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 1\u201313, Santa Barbara, CA, USA, August 19\u201323, 2012. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-642-32009-5_1.","DOI":"10.1007\/978-3-642-32009-5_1"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Marc Kaplan, Ga\u00ebtan Leurent, Anthony Leverrier, and Mar\u00eda Naya-Plasencia. Breaking symmetric cryptosystems using quantum period finding. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology \u2013 CRYPTO 2016, Part II, volume 9815 of Lecture Notes in Computer Science, pages 207\u2013237, Santa Barbara, CA, USA, August 14\u201318, 2016. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-662-53008-5_8.","DOI":"10.1007\/978-3-662-53008-5_8"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u20132685, 2010. https:\/\/doi.org\/10.1109\/ISIT.2010.5513654.","DOI":"10.1109\/ISIT.2010.5513654"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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\u20136, 2024, Proceedings, Part II, pages 3\u201335, Cham, 2025. Springer Nature Switzerland. https:\/\/doi.org\/10.1007\/978-3-031-78017-2_1.","DOI":"10.1007\/978-3-031-78017-2_1"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1137\/0217022"},{"key":"29","unstructured":"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."},{"key":"30","unstructured":"Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In STOC 2025 (to appear), 2025. https:\/\/arxiv.org\/abs\/2410.10116."},{"key":"31","doi-asserted-by":"publisher","unstructured":"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\u2013412, Baltimore, MA, USA, May 22\u201324, 2005. ACM Press. https:\/\/doi.org\/10.1145\/1060590.1060651.","DOI":"10.1145\/1060590.1060651"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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 \u2013 EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 311\u2013326, Copenhagen, Denmark, May 11\u201315, 2014. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-642-55220-5_18.","DOI":"10.1007\/978-3-642-55220-5_18"},{"key":"33","doi-asserted-by":"publisher","unstructured":"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 \u2013 CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 392\u2013409, Santa Barbara, CA, USA, August 18\u201322, 2013. Springer Berlin Heidelberg, Germany. https:\/\/doi.org\/10.1007\/978-3-642-40041-4_22.","DOI":"10.1007\/978-3-642-40041-4_22"},{"key":"34","unstructured":"Fang Song. Quantum-secure pseudorandom permutations, 2017. Blog post: https:\/\/qcc.fangsong.info\/2017-06-quantumprp."},{"key":"35","unstructured":"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."},{"key":"36","doi-asserted-by":"publisher","unstructured":"Mark Zhandry. How to construct quantum random functions. In 53rd Annual Symposium on Foundations of Computer Science, pages 679\u2013687, New Brunswick, NJ, USA, October 20\u201323, 2012. IEEE Computer Society Press. https:\/\/doi.org\/10.1109\/FOCS.2012.37.","DOI":"10.1109\/FOCS.2012.37"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Mark Zhandry. Redeeming reset indifferentiability and applications to post-quantum security. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology \u2013 ASIACRYPT 2021, Part I, volume 13090 of Lecture Notes in Computer Science, pages 518\u2013548, Singapore, December 6\u201310, 2021. Springer, Cham, Switzerland. https:\/\/doi.org\/10.1007\/978-3-030-92062-3_18.","DOI":"10.1007\/978-3-030-92062-3_18"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-04-08-1696\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T13:10:06Z","timestamp":1744117806000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-04-08-1696\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":38,"URL":"https:\/\/doi.org\/10.22331\/q-2025-04-08-1696","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"article-number":"1696"}}