{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:37Z","timestamp":1781078257747,"version":"3.54.1"},"reference-count":31,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,1,9]],"date-time":"2024-01-09T00:00:00Z","timestamp":1704758400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,3,5]]},"abstract":"<jats: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\u2014except 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\u2014provided it cannot query the challenge itself. <\/jats:p>","DOI":"10.62056\/a0qj89n4e","type":"journal-article","created":{"date-parts":[[2024,4,9]],"date-time":"2024-04-09T19:27:10Z","timestamp":1712690830000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":6,"title":["On the Two-sided Permutation Inversion Problem"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0107-6037","authenticated-orcid":false,"given":"Gorjan","family":"Alagic","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/047s2c258","id-type":"ROR","asserted-by":"publisher"}],"name":"QuICS, University of Maryland","place":["USA"]},{"id":[{"id":"https:\/\/ror.org\/05xpvk416","id-type":"ROR","asserted-by":"publisher"}],"name":"National Institute of Standards and Technology","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1208-7935","authenticated-orcid":false,"given":"Chen","family":"Bai","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/047s2c258","id-type":"ROR","asserted-by":"publisher"}],"name":"QuICS, University of Maryland","place":["USA"]},{"id":[{"id":"https:\/\/ror.org\/047s2c258","id-type":"ROR","asserted-by":"publisher"}],"name":"Dept. of Electrical and Computer Engineering, University of Maryland","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7330-1539","authenticated-orcid":false,"given":"Alexander","family":"Poremba","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05dxps055","id-type":"ROR","asserted-by":"publisher"}],"name":"Computing and Mathematical Sciences, California Institute of Technology","place":["USA"]},{"id":[{"id":"https:\/\/ror.org\/042nb2s44","id-type":"ROR","asserted-by":"publisher"}],"name":"CSAIL and Department of Mathematics, Massachusetts Institute of Technology","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0845-1506","authenticated-orcid":false,"given":"Kaiyan","family":"Shi","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/047s2c258","id-type":"ROR","asserted-by":"publisher"}],"name":"QuICS, University of Maryland","place":["USA"]},{"id":[{"id":"https:\/\/ror.org\/047s2c258","id-type":"ROR","asserted-by":"publisher"}],"name":"Dept. of Computer Science, University of Maryland","place":["USA"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,4,9]]},"reference":[{"key":"ref1:grover1996fast","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1145\/237814.237866","article-title":"A fast quantum mechanical algorithm for database search","volume-title":"Proceedings of the twenty-eighth annual ACM symposium on\n  Theory of computing","author":"Lov K Grover","year":"1996"},{"key":"ref2:ambainis2002quantum","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1006\/jcss.2002.1826","article-title":"Quantum lower bounds by quantum arguments","volume":"64","author":"Andris Ambainis","year":"2002","journal-title":"Journal of Computer and System Sciences"},{"key":"ref3:bennett1997strengths","doi-asserted-by":"crossref","first-page":"1510","DOI":"10.1137\/S0097539796300933","article-title":"Strengths and weaknesses of quantum computing","volume":"26","author":"Charles H Bennett","year":"1997","journal-title":"SIAM journal on Computing"},{"key":"ref4:nayak2010inverting","article-title":"Inverting a permutation is as hard as unordered search","author":"Ashwin Nayak","year":"2010","journal-title":"arXiv preprint arXiv:1007.2899"},{"key":"ref5:katz2020introduction","article-title":"Introduction to modern cryptography","author":"Jonathan Katz","year":"2020"},{"key":"ref6:guido2011cryptographic","article-title":"Cryptographic sponge functions","author":"Bertoni Guido","year":"2011"},{"key":"ref7:hhan2019quantum","first-page":"584","article-title":"Quantum random oracle model with auxiliary input","volume-title":"International Conference on the Theory and Application of\n  Cryptology and Information Security","author":"Minki Hhan","year":"2019"},{"key":"ref8:chung2019lower","article-title":"Lower bounds for function inversion with quantum advice","author":"Kai-Min Chung","year":"2019","journal-title":"arXiv preprint arXiv:1911.09176"},{"key":"ref9:chung2020tight","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1109\/FOCS46700.2020.00068","article-title":"Tight quantum time-space tradeoffs for function inversion","volume-title":"2020 IEEE 61st Annual Symposium on Foundations of Computer\n  Science (FOCS)","author":"Kai-Min Chung","year":"2020"},{"key":"ref10:dunkelman2023quantum","first-page":"1","article-title":"Quantum time\/memory\/data tradeoff attacks","author":"Orr Dunkelman","year":"2023","journal-title":"Designs, Codes and Cryptography"},{"key":"ref11:liu2023non","first-page":"117","article-title":"Non-uniformity and Quantum Advice in the Quantum Random\n  Oracle Model","volume-title":"Annual International Conference on the Theory and\n  Applications of Cryptographic Techniques","author":"Qipeng Liu","year":"2023"},{"key":"ref12:rosmanis2021tight","article-title":"Tight bounds for inverting permutations via compressed\n  oracle arguments","author":"Ansis Rosmanis","year":"2021","journal-title":"arXiv preprint arXiv:2103.08975"},{"key":"ref13:nayebi2014quantum","article-title":"Quantum lower bound for inverting a permutation with\n  advice","author":"Aran Nayebi","year":"2014","journal-title":"arXiv preprint arXiv:1408.3193"},{"key":"ref14:fefferman2015quantum","article-title":"Quantum vs classical proofs and subset verification","author":"Bill Fefferman","year":"2015","journal-title":"arXiv preprint arXiv:1510.06750"},{"key":"ref15:belovs2023one","article-title":"One-Way Ticket to Las Vegas and the Quantum Adversary","author":"Aleksandrs Belovs","year":"2023","journal-title":"arXiv preprint arXiv:2301.02003"},{"key":"ref16:cao2021being","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.tcs.2020.11.013","article-title":"Being a permutation is also orthogonal to one-wayness in\n  quantum world: Impossibilities of quantum one-way permutations from\n  one-wayness primitives","volume":"855","author":"Shujiao Cao","year":"2021","journal-title":"Theoretical Computer Science"},{"key":"ref17:zhandry2019record","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/978-3-030-26951-7_9","article-title":"How to record quantum queries, and applications to quantum\n  indifferentiability","volume-title":"Advances in Cryptology\u2013CRYPTO 2019: 39th Annual\n  International Cryptology Conference, Santa Barbara, CA, USA, August 18\u201322,\n  2019, Proceedings, Part II 39","author":"Mark Zhandry","year":"2019"},{"key":"ref18:alagic2022post","first-page":"458","article-title":"Post-quantum security of the Even-Mansour cipher","volume-title":"Annual International Conference on the Theory and\n  Applications of Cryptographic Techniques","author":"Gorjan Alagic","year":"2022"},{"key":"ref19:alagic2022posttwk","article-title":"Post-Quantum Security of the (Tweakable) FX Construction,\n  and Applications","author":"Gorjan Alagic","year":"2022","journal-title":"Cryptology ePrint Archive"},{"key":"ref20:Vaz98","article-title":"On the power of quantum computation","author":"Umesh Vazirani","year":"1998","journal-title":"Philosophical Transactions of the Royal Society of London A\n  365: 1759-1768"},{"key":"ref21:Wiesner83","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1145\/1008908.1008920","article-title":"Conjugate coding","volume":"15","author":"Stephen Wiesner","year":"1983","journal-title":"ACM Sigact News"},{"key":"ref22:ambainis1999dense","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1145\/301250.301347","article-title":"Dense quantum coding and a lower bound for 1-way quantum\n  automata","volume-title":"Proceedings of the thirty-first annual ACM symposium on\n  Theory of computing","author":"Andris Ambainis","year":"1999"},{"key":"ref23:ambainis2008quantum","article-title":"Quantum random access codes with shared randomness","author":"Andris Ambainis","year":"2008","journal-title":"arXiv preprint arXiv:0810.2937"},{"key":"ref24:ambainis2019quantum","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/978-3-030-26951-7_10","article-title":"Quantum security proofs using semi-classical oracles","volume-title":"Advances in Cryptology\u2013CRYPTO 2019: 39th Annual\n  International Cryptology Conference, Santa Barbara, CA, USA, August 18\u201322,\n  2019, Proceedings, Part II 39","author":"Andris Ambainis","year":"2019"},{"key":"ref25:dohotaru2008exact","article-title":"Exact quantum lower bound for Grover's problem","author":"Catalin Dohotaru","year":"2008","journal-title":"arXiv preprint arXiv:0810.3647"},{"key":"ref26:zalka1999grover","doi-asserted-by":"crossref","first-page":"2746","DOI":"10.1103\/PhysRevA.60.2746","article-title":"Grover\u2019s quantum searching algorithm is optimal","volume":"60","author":"Christof Zalka","year":"1999","journal-title":"Physical Review A"},{"key":"ref27:zhandry2016note","article-title":"A note on quantum-secure PRPs","author":"Mark Zhandry","year":"2016","journal-title":"arXiv preprint arXiv:1611.05564"},{"key":"ref28:regev2009lattices","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and\n  cryptography","volume":"56","author":"Oded Regev","year":"2009","journal-title":"Journal of the ACM (JACM)"},{"key":"ref29:dworkin2015sha","article-title":"SHA-3 standard: Permutation-based hash and extendable-output\n  functions","author":"Morris J Dworkin","year":"2015","journal-title":"Federal Inf. Process. Stds. (NIST FIPS)"},{"key":"ref30:czajkowski2018post","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/978-3-319-79063-3_9","article-title":"Post-quantum security of the sponge construction","volume-title":"International Conference on Post-Quantum Cryptography","author":"Jan Czajkowski","year":"2018"},{"key":"ref31:czajkowski2021quantum","article-title":"Quantum lazy sampling and game-playing proofs for quantum\n  indifferentiability","author":"Jan Czajkowski","year":"2021","journal-title":"arXiv preprint arXiv:1904.11477"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:25:17Z","timestamp":1733865917000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/1\/27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,9]]},"references-count":31,"URL":"https:\/\/doi.org\/10.62056\/a0qj89n4e","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,9]]},"assertion":[{"value":"2024-01-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-1-84"}}