Communications in Cryptology IACR CiC

On the Two-sided Permutation Inversion Problem


Gorjan Alagic, Chen Bai, Alexander Poremba, Kaiyan Shi
Gorjan Alagic ORCID
QuICS, University of Maryland, USA
National Institute of Standards and Technology, USA
galagic at umd dot edu
Chen Bai ORCID
QuICS, University of Maryland, USA
Dept. of Electrical and Computer Engineering, University of Maryland, USA
cbai1 at umd dot edu
Alexander Poremba ORCID
Computing and Mathematical Sciences, California Institute of Technology, USA
CSAIL and Department of Mathematics, Massachusetts Institute of Technology, USA
poremba at mit dot edu
Kaiyan Shi ORCID
QuICS, University of Maryland, USA
Dept. of Computer Science, University of Maryland, USA
kshi12 at umd dot edu


In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This fundamental problem in query complexity appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation—except that the challenge value cannot be submitted to the latter. Within that setting, we consider three options for the inversion algorithm: whether it can get quantum advice about the permutation, whether the query algorithm can restrict the distribution with which the challenge input is sampled, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the permutation inversion problem and establish lower bounds for them. Our results show that, perhaps surprisingly, the permutation inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse—provided it cannot query the challenge itself.


Gorjan Alagic, Chen Bai, Jonathan Katz, Christian Majenz, and Patrick Struck. Post-quantum security of the (tweakable) fx construction, and applications. Cryptology ePrint Archive, 2022.
Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz. Post-quantum security of the even-mansour cipher. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, 458–487. Springer, 2022.
Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II 39, 269–295. Springer, 2019.
Andris Ambainis, Debbie Leung, Laura Mancinska, and Maris Ozols. Quantum random access codes with shared randomness. arXiv preprint arXiv:0810.2937, 2008.
Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750–767, 2002.
Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani. Dense quantum coding and a lower bound for 1-way quantum automata. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, 376–383. 1999.
Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510–1523, 1997.
Aleksandrs Belovs and Duyal Yolcu. One-way ticket to las vegas and the quantum adversary. arXiv preprint arXiv:2301.02003, 2023.
Jan Czajkowski, Leon Groot Bruinderink, Andreas Hülsing, Christian Schaffner, and Dominique Unruh. Post-quantum security of the sponge construction. In International Conference on Post-Quantum Cryptography, 185–204. Springer, 2018.
Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. Tight quantum time-space tradeoffs for function inversion. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 673–684. IEEE, 2020.
Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower bounds for function inversion with quantum advice. arXiv preprint arXiv:1911.09176, 2019.
Jan Czajkowski, Christian Majenz, Christian Schaffner, and Sebastian Zur. Quantum lazy sampling and game-playing proofs for quantum indifferentiability. arXiv preprint arXiv:1904.11477, 2021.
Shujiao Cao and Rui Xue. Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives. Theoretical Computer Science, 855:16–42, 2021.
Catalin Dohotaru and Peter Hoyer. Exact quantum lower bound for grover's problem. arXiv preprint arXiv:0810.3647, 2008.
Orr Dunkelman, Nathan Keller, Eyal Ronen, and Adi Shamir. Quantum time/memory/data tradeoff attacks. Designs, Codes and Cryptography, pages 1–19, 2023.
Morris J Dworkin. Sha-3 standard: permutation-based hash and extendable-output functions. Federal Inf. Process. Stds. (NIST FIPS), 2015.
Bill Fefferman and Shelby Kimmel. Quantum vs classical proofs and subset verification. arXiv preprint arXiv:1510.06750, 2015.
Bertoni Guido, Daemen Joan, P Michaël, and VA Gilles. Cryptographic sponge functions. 2011.
Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, 212–219. 1996.
Minki Hhan, Keita Xagawa, and Takashi Yamakawa. Quantum random oracle model with auxiliary input. In International Conference on the Theory and Application of Cryptology and Information Security, 584–614. Springer, 2019.
Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2020.
Qipeng Liu. Non-uniformity and quantum advice in the quantum random oracle model. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, 117–143. Springer, 2023.
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan. Quantum lower bound for inverting a permutation with advice. arXiv preprint arXiv:1408.3193, 2014.
Ashwin Nayak. Inverting a permutation is as hard as unordered search. arXiv preprint arXiv:1007.2899, 2010.
Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009.
Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. arXiv preprint arXiv:2103.08975, 2021.
Umesh Vazirani. On the power of quantum computation. Philosophical Transactions of the Royal Society of London A 365: 1759-1768, 1998.
Stephen Wiesner. Conjugate coding. ACM Sigact News, 15(1):78–88, 1983.
Christof Zalka. Grover’s quantum searching algorithm is optimal. Physical Review A, 60(4):2746, 1999.
Mark Zhandry. A note on quantum-secure prps. arXiv preprint arXiv:1611.05564, 2016.
Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II 39, 239–268. Springer, 2019.

PDFPDF Open access

Submitted: 2024-01-09
Accepted: 2024-03-05
Published: 2024-04-09
How to cite

Gorjan Alagic, Chen Bai, Alexander Poremba, and Kaiyan Shi, "On the Two-sided Permutation Inversion Problem," IACR Communications in Cryptology, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a0qj89n4e.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.