On the Two-sided Permutation Inversion Problem

Gorjan Alagic; Chen Bai; Alexander Poremba; Kaiyan Shi

doi:10.62056/a0qj89n4e

On the Two-sided Permutation Inversion Problem

Authors

Gorjan Alagic, Chen Bai, Alexander Poremba, Kaiyan Shi

Gorjan Alagic

QuICS, University of Maryland, USA
National Institute of Standards and Technology, USA
galagic at umd dot edu

Chen Bai

QuICS, University of Maryland, USA
Dept. of Electrical and Computer Engineering, University of Maryland, USA
cbai1 at umd dot edu

Alexander Poremba

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

QuICS, University of Maryland, USA
Dept. of Computer Science, University of Maryland, USA
kshi12 at umd dot edu

Abstract

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.

References

[ABK⁺22]

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.

Google Scholar ePrint

[ABKM22]

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. https://doi.org/https://doi.org/10.1007/978-3-031-07082-2_17.

Google Scholar ePrint

[AHU19]

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. https://doi.org/https://doi.org/10.1007/978-3-030-26951-7_10.

Google Scholar ePrint

[ALMO08]

Andris Ambainis, Debbie Leung, Laura Mancinska, and Maris Ozols. Quantum random access codes with shared randomness. arXiv preprint arXiv:0810.2937, 2008. https://doi.org/https://doi.org/10.48550/arXiv.0810.2937.

Google Scholar ePrint

[Amb02]

Andris Ambainis. Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences, 64(4):750–767, 2002. https://doi.org/https://doi.org/10.1145/335305.335394.

Google Scholar ePrint

[ANTSV99]

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. https://doi.org/https://doi.org/10.1145/301250.301347.

Google Scholar ePrint

[BBBV97]

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. https://doi.org/https://doi.org/10.1137/S0097539796300933.

Google Scholar ePrint

[BY23]

Aleksandrs Belovs and Duyal Yolcu. One-way ticket to las vegas and the quantum adversary. arXiv preprint arXiv:2301.02003, 2023. https://doi.org/https://doi.org/10.48550/arXiv.2301.02003.

Google Scholar ePrint

[CGBH⁺18]

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. https://doi.org/https://doi.org/10.1007/978-3-319-79063-3_9.

Google Scholar ePrint

[CGLQ20]

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. https://doi.org/10.1109/FOCS46700.2020.00068.

Google Scholar ePrint

[CLQ19]

Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower bounds for function inversion with quantum advice. arXiv preprint arXiv:1911.09176, 2019. https://doi.org/https://doi.org/10.48550/arXiv.1911.09176.

Google Scholar ePrint

[CMSZ21]

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. https://doi.org/https://doi.org/10.48550/arXiv.1904.11477.

Google Scholar ePrint

[CX21]

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. https://doi.org/https://doi.org/10.1016/j.tcs.2020.11.013.

Google Scholar ePrint

[DH08]

Catalin Dohotaru and Peter Hoyer. Exact quantum lower bound for grover's problem. arXiv preprint arXiv:0810.3647, 2008. https://doi.org/https://doi.org/10.26421/QIC9.5-6-12.

Google Scholar ePrint

[DKRS23]

Orr Dunkelman, Nathan Keller, Eyal Ronen, and Adi Shamir. Quantum time/memory/data tradeoff attacks. Designs, Codes and Cryptography, pages 1–19, 2023. https://doi.org/https://doi.org/10.1007/s10623-023-01300-x.

Google Scholar ePrint

[Dwo15]

Morris J Dworkin. Sha-3 standard: permutation-based hash and extendable-output functions. Federal Inf. Process. Stds. (NIST FIPS), 2015. https://doi.org/https://doi.org/10.6028/NIST.FIPS.202.

Google Scholar ePrint

[FK15]

Bill Fefferman and Shelby Kimmel. Quantum vs classical proofs and subset verification. arXiv preprint arXiv:1510.06750, 2015. https://doi.org/https://doi.org/10.48550/arXiv.1510.06750.

Google Scholar ePrint

[GJMG11]

Bertoni Guido, Daemen Joan, P Michaël, and VA Gilles. Cryptographic sponge functions. 2011.

Google Scholar ePrint

[Gro96]

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. https://doi.org/https://doi.org/10.1145/237814.237866.

Google Scholar ePrint

[HXY19]

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. https://doi.org/https://doi.org/10.1007/978-3-030-34578-5_21.

Google Scholar ePrint

[KL20]

Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography. CRC press, 2020. https://doi.org/https://doi.org/10.1201/9781420010756.

Google Scholar ePrint

[Liu23]

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. https://doi.org/https://doi.org/10.1007/978-3-031-30545-0_5.

Google Scholar ePrint

[NABT14]

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan. Quantum lower bound for inverting a permutation with advice. arXiv preprint arXiv:1408.3193, 2014. https://doi.org/https://doi.org/10.48550/arXiv.1408.3193.

Google Scholar ePrint

[Nay10]

Ashwin Nayak. Inverting a permutation is as hard as unordered search. arXiv preprint arXiv:1007.2899, 2010. https://doi.org/https://doi.org/10.48550/arXiv.1007.2899.

Google Scholar ePrint

[Reg09]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1–40, 2009. https://doi.org/https://doi.org/10.1145/1568318.1568324.

Google Scholar ePrint

[Ros21]

Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. arXiv preprint arXiv:2103.08975, 2021. https://doi.org/https://doi.org/10.48550/arXiv.2103.08975.

Google Scholar ePrint

[Vaz98]

Umesh Vazirani. On the power of quantum computation. Philosophical Transactions of the Royal Society of London A 365: 1759-1768, 1998. https://doi.org/https://doi.org/10.1137/S0097539796298637.

Google Scholar ePrint

[Wie83]

Stephen Wiesner. Conjugate coding. ACM Sigact News, 15(1):78–88, 1983. https://doi.org/https://doi.org/10.1145/1008908.1008920.

Google Scholar ePrint

[Zal99]

Christof Zalka. Grover’s quantum searching algorithm is optimal. Physical Review A, 60(4):2746, 1999. https://doi.org/https://doi.org/10.1103/PhysRevA.60.2746.

Google Scholar ePrint

[Zha16]

Mark Zhandry. A note on quantum-secure prps. arXiv preprint arXiv:1611.05564, 2016. https://doi.org/https://doi.org/10.48550/arXiv.1611.05564.

Google Scholar ePrint

[Zha19]

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. https://doi.org/https://doi.org/10.1007/978-3-030-26951-7_9.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a0qj89n4e

History

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.

License

Copyright is held by the author(s)

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

@article{CiC-1-1-27,
    author = "Alagic, Gorjan and Bai, Chen and Poremba, Alexander and Shi, Kaiyan",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "On the Two-sided Permutation Inversion Problem",
    volume = "1",
    number = "1",
    date = "2024-04-09",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a0qj89n4e"
}

TY - JOUR
AU - Alagic, Gorjan
AU - Bai, Chen
AU - Poremba, Alexander
AU - Shi, Kaiyan
PY  - 2024
TI  - On the Two-sided Permutation Inversion Problem
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 1
DO  - 10.62056/a0qj89n4e
UR  - https://doi.org/10.62056/a0qj89n4e
AB  - <p>  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. </p>
ER  -

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.