CINXE.COM
On the Two-sided Permutation Inversion Problem
<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"> <link href="/css/bootstrap/css/bootstrap.min.css" rel="stylesheet"> <script src="/css/bootstrap/js/bootstrap.bundle.min.js"></script> <title>On the Two-sided Permutation Inversion Problem</title> <link rel="stylesheet" href="/css/iacrcc.css"> <link rel="icon" type="image/png" href="/favicon.ico"> <style> div.authorname { font-weight: 500; margin-bottom: .3rem; } div.author { margin-bottom: 1rem; } span.keyword { font-weight: 500; } span.keyword a { color: black; } div.reference { margin-bottom: .5rem; } ol.bib li:before { margin-left: -1.5rem; content: "[" counter(bcounter) "] "; margin-right: .5rem; } ol.bib { list-style: none; counter-reset: bcounter; } ol.bib li { counter-increment: bcounter; margin-bottom: .5rem; } .card-header { background-color: #d1e7dd !important; } .authorlist { /* border: 1px solid #aaa; padding: 1rem; margin-bottom: 1rem; background-color: white;*/ } </style> <script> MathJax = { tex: { inlineMath: [['$', '$'], ['\\(', '\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEnvironments: false, processEscapes: true }, "HTML-CSS": { linebreaks: { automatic: true } } }; </script> <script id="MathJax-script" async src="/js/mathjax/tex-chtml.js"></script> <link rel="schema.DC" href="http://purl.org/dc/elements/1.1/"> <meta name="DC.Creator.PersonalName" content="Gorjan Alagic"> <meta name="DC.Creator.PersonalName" content="Chen Bai"> <meta name="DC.Creator.PersonalName" content="Alexander Poremba"> <meta name="DC.Creator.PersonalName" content="Kaiyan Shi"> <meta name="DC.Date.created" content="2024-04-09 19:26:57"> <meta name="DC.Date.dateSubmitted" content="2024-01-09"> <meta name="DC.Date.dateAccepted" content="2024-03-05"> <meta name="DC.Description" xml:lang="en" lang="en" content="<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>"> <meta name="DC.Format" content="application/pdf"> <meta name="DC.Identifier.DOI" content="10.62056/a0qj89n4e"> <meta name="DC.Identifier.URI" content="https://cic.iacr.org/p/1/1/27"> <meta name="DC.Language" content="en"> <meta name="DC.Rights" content="Copyright (c) 2023 held by author(s)"> <meta name="DC.Rights" content="https://creativecommons.org/licenses/by/4.0/"> <meta name="DC.Source" content="IACR Communications in Cryptology"> <meta name="DC.Source.ISSN" content="3006-5496"> <meta name="DC.Source.Issue" content="1"> <meta name="DC.Source.Volume" content="1"><meta name="DC.Title" content="On the Two-sided Permutation Inversion Problem"> <meta name="DC.Type" content="Text.Serial.Journal"> <meta name="DC.Type.articleType" content="Articles"> <meta name="citation_journal_title" content="IACR Communications in Cryptology"> <meta name="citation_journal_abbrev" content="CiC"> <meta name="citation_issn" content="3006-5496"><meta name="citation_author" content="Gorjan Alagic"> <meta name="citation_author_institution" content="QuICS, University of Maryland"> <meta name="citation_author_institution" content="National Institute of Standards and Technology"> <meta name="citation_author" content="Chen Bai"> <meta name="citation_author_institution" content="QuICS, University of Maryland"> <meta name="citation_author_institution" content="Dept. of Electrical and Computer Engineering, University of Maryland"> <meta name="citation_author" content="Alexander Poremba"> <meta name="citation_author_institution" content="Computing and Mathematical Sciences, California Institute of Technology"> <meta name="citation_author_institution" content="CSAIL and Department of Mathematics, Massachusetts Institute of Technology"> <meta name="citation_author" content="Kaiyan Shi"> <meta name="citation_author_institution" content="QuICS, University of Maryland"> <meta name="citation_author_institution" content="Dept. of Computer Science, University of Maryland"> <meta name="citation_title" content="On the Two-sided Permutation Inversion Problem"> <meta name="citation_language" content="en"> <meta name="citation_date" content="2024-04-09"> <meta name="citation_volume" content="1"> <meta name="citation_issue" content="1"> <meta name="citation_doi" content="10.62056/a0qj89n4e"> <meta name="citation_abstract_html_url" content="https://cic.iacr.org/p/1/1/27"> <meta name="citation_pdf_url" content="https://cic.iacr.org/p/1/1/27/pdf"> </head> <body> <noscript> <h1 class="text-center">What a lovely hat</h1> <h4 class="text-center">Is it made out of <a href="https://iacr.org/tinfoil.html">tin foil</a>?</h4> </noscript> <div class="pageTop d-flex justify-content-md-around justify-content-between align-items-center"> <a href="https://iacr.org"><img id="logo" class="d-none d-lg-block ms-5" src="/images/iacrlogo_small.png" title="International Association for Cryptologic Research" alt="IACR logo"></a> <span class="headerTitle d-none d-md-block">Communications in Cryptology</span> <span class="headerTitle d-md-none">IACR CiC</span> <div class="dropdown ps-lg-2 me-5"> <button class="btn border-0" type="button" id="dropdownMenuButton1" data-bs-toggle="dropdown" aria-expanded="true"> <img src="/images/search.svg" class="searchIcon" alt="Search Button" style="width:33px;"> </button> <div id="searchDd" class="dropdown-menu dropdown-menu-end bg-transparent border-0" aria-labelledby="dropdownMenuButton1" data-bs-popper="none"> <form action="/search" method="GET" class="me-3"> <div class="input-group"> <input id="searchbox" name="q" type="search" class="form-control shadow-none" autocomplete="off" > <input type="hidden" name="d" value="/var/www/wsgi/cicjournal/webapp/search_index/xapian.db"> <button class="btn btn-outline-dark border border-dark input-group-append"> Search </button> </div> </form> <div id="results" class="bg-light"></div> </div> </div> </div> <nav id="sitenav" class="navbar navbar-expand-md"> <div class="container"> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#collapseContent" aria-controls="collapseContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="collapseContent"> <ul class="navbar-nav nav-fill w-100 justify-content-between"> <li class="nav-item"> <a class="nav-link active" aria-current="page" href="/">Home</a> </li> <li class="nav-item"> <a class="nav-link" href="/contents">Papers</a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"> Submissions </a> <ul class="dropdown-menu ms-3 ms-lg-5"> <li><a class="dropdown-item" href="/callforpapers">Call for papers</a></li> <li><a class="dropdown-item" href="/ethics">Publication ethics</a></li> <li><a class="dropdown-item" href="/irregular">Irregular submissions</a></li> <li><a class="dropdown-item" href="/conflicts">Conflict of interest</a></li> <li><a class="dropdown-item" href="/retraction">Retraction policy</a></li> </ul> </li> <li class="nav-item"> <a class="nav-link" href="/faq">FAQ</a> </li> <li class="nav-item"> <a class="nav-link" href="/contact">Contact</a> </li> <li class="nav-item"> <a class="nav-link" href="/board">Editorial board</a> </li> <li class="nav-item dropdown"> <a href="#" class="ms-md-5 nav-link dropdown-toggle" data-bs-toggle="dropdown"><img alt="Login" src="/images/user.svg"></a> <ul class="dropdown-menu"> <li><a href="/login" class="dropdown-item">Admin login</a></li> </ul> </li> </ul> </div> </div> </nav> <main id="mainContent" class="container"> <nav aria-label="breadcrumb" class="mt-3"> <ol class="breadcrumb"> <li class="breadcrumb-item"><a href="/">Home</a></li> <li class="breadcrumb-item"><a href="/v/1">Volume 1</a></li> <li class="breadcrumb-item"><a href="/i/1/1">Issue 1</a></li> <li class="breadcrumb-item active" aria-current="page">27</li> </ol> </nav> <h2>On the Two-sided Permutation Inversion Problem</h2> <div class="row mt-3"> <div class="col-12 col-md-8"> <h3 class="mt-2">Authors</h3> <div class="fs-4 mb-4 mt-2 d-flex justify-content-between flex-column flex-lg-row"> <div>Gorjan Alagic, Chen Bai, Alexander Poremba, Kaiyan Shi</div> <button role="button" aria-expanded="false" aria-controls="authorlist" class="ms-4 btn me-3 dropdown-toggle" data-bs-toggle="collapse" data-bs-target="#authorlist">Author Info</button> </div> <div id="authorlist" class="authorlist collapse"> <div class="author"> <div class="authorname">Gorjan Alagic <a target="_blank" href="https://orcid.org/0000-0002-0107-6037"><img alt="ORCID" class="align-baseline orcidIcon" src="/images/orcid.svg"></a> </div> <div class="ms-4 mb-2"> QuICS, University of Maryland, USA<br> National Institute of Standards and Technology, USA<br> <span class="font-monospace">galagic at umd dot edu</span> </div> </div> <div class="author"> <div class="authorname">Chen Bai <a target="_blank" href="https://orcid.org/0000-0003-1208-7935"><img alt="ORCID" class="align-baseline orcidIcon" src="/images/orcid.svg"></a> </div> <div class="ms-4 mb-2"> QuICS, University of Maryland, USA<br> Dept. of Electrical and Computer Engineering, University of Maryland, USA<br> <span class="font-monospace">cbai1 at umd dot edu</span> </div> </div> <div class="author"> <div class="authorname">Alexander Poremba <a target="_blank" href="https://orcid.org/0000-0002-7330-1539"><img alt="ORCID" class="align-baseline orcidIcon" src="/images/orcid.svg"></a> </div> <div class="ms-4 mb-2"> Computing and Mathematical Sciences, California Institute of Technology, USA<br> CSAIL and Department of Mathematics, Massachusetts Institute of Technology, USA<br> <span class="font-monospace">poremba at mit dot edu</span> </div> </div> <div class="author"> <div class="authorname">Kaiyan Shi <a target="_blank" href="https://orcid.org/0000-0002-0845-1506"><img alt="ORCID" class="align-baseline orcidIcon" src="/images/orcid.svg"></a> </div> <div class="ms-4 mb-2"> QuICS, University of Maryland, USA<br> Dept. of Computer Science, University of Maryland, USA<br> <span class="font-monospace">kshi12 at umd dot edu</span> </div> </div> </div> <h3 class="mt-4">Abstract</h3> <p><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></p> <h3 class="mb-3">References</h3> <div class="d-flex"> <div style="min-width:9rem;">[ABK<sup>+</sup>22]</div> <div>Gorjan Alagic, Chen Bai, Jonathan Katz, Christian Majenz, and Patrick Struck. <a href="https://eprint.iacr.org/2022/1097">Post-quantum security of the (tweakable) fx construction, and applications.</a> <em>Cryptology ePrint Archive</em>, 2022.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Alagic%2C+Gorjan%2C+Bai%2C+Chen%2C+Katz%2C+Jonathan%2C+Majenz%2C+Christian%2C+and+%0AStruck%2C+Patrick+Post-Quantum+Security+of+the+%28Tweakable%29+FX+Construction%2C+and+Applications+2022" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Alagic%2C+Gorjan%2C+Bai%2C+Chen%2C+Katz%2C+Jonathan%2C+Majenz%2C+Christian%2C+and+%0AStruck%2C+Patrick&title=Post-Quantum+Security+of+the+%28Tweakable%29+FX+Construction%2C+and+Applications&submittedafter=2021&submittedbefore=2023" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[ABKM22]</div> <div>Gorjan Alagic, Chen Bai, Jonathan Katz, and Christian Majenz. Post-quantum security of the even-mansour cipher. In <em>Annual International Conference on the Theory and Applications of Cryptographic Techniques</em>, 458–487. Springer, 2022. <a href="https://doi.org/https://doi.org/10.1007/978-3-031-07082-2_17">https://doi.org/https://doi.org/10.1007/978-3-031-07082-2_17</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Alagic%2C+Gorjan%2C+Bai%2C+Chen%2C+Katz%2C+Jonathan%2C+and+%0AMajenz%2C+Christian+Post-quantum+security+of+the+Even-Mansour+cipher+2022" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Alagic%2C+Gorjan%2C+Bai%2C+Chen%2C+Katz%2C+Jonathan%2C+and+%0AMajenz%2C+Christian&title=Post-quantum+security+of+the+Even-Mansour+cipher&submittedafter=2021&submittedbefore=2023" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[AHU19]</div> <div>Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In <em>Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II 39</em>, 269–295. Springer, 2019. <a href="https://doi.org/https://doi.org/10.1007/978-3-030-26951-7_10">https://doi.org/https://doi.org/10.1007/978-3-030-26951-7_10</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Ambainis%2C+Andris%2C+Hamburg%2C+Mike%2C+and+%0AUnruh%2C+Dominique+Quantum+security+proofs+using+semi-classical+oracles+2019" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Ambainis%2C+Andris%2C+Hamburg%2C+Mike%2C+and+%0AUnruh%2C+Dominique&title=Quantum+security+proofs+using+semi-classical+oracles&submittedafter=2018&submittedbefore=2020" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[ALMO08]</div> <div>Andris Ambainis, Debbie Leung, Laura Mancinska, and Maris Ozols. Quantum random access codes with shared randomness. <em>arXiv preprint arXiv:0810.2937</em>, 2008. <a href="https://doi.org/https://doi.org/10.48550/arXiv.0810.2937">https://doi.org/https://doi.org/10.48550/arXiv.0810.2937</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Ambainis%2C+Andris%2C+Leung%2C+Debbie%2C+Mancinska%2C+Laura%2C+and+%0AOzols%2C+Maris+Quantum+random+access+codes+with+shared+randomness+2008" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Ambainis%2C+Andris%2C+Leung%2C+Debbie%2C+Mancinska%2C+Laura%2C+and+%0AOzols%2C+Maris&title=Quantum+random+access+codes+with+shared+randomness&submittedafter=2007&submittedbefore=2009" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Amb02]</div> <div>Andris Ambainis. Quantum lower bounds by quantum arguments. <em>Journal of Computer and System Sciences</em>, 64(4):750–767, 2002. <a href="https://doi.org/https://doi.org/10.1145/335305.335394">https://doi.org/https://doi.org/10.1145/335305.335394</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Ambainis%2C+Andris+Quantum+lower+bounds+by+quantum+arguments+2002" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Ambainis%2C+Andris&title=Quantum+lower+bounds+by+quantum+arguments&submittedafter=2001&submittedbefore=2003" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[ANTSV99]</div> <div>Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma, and Umesh Vazirani. Dense quantum coding and a lower bound for 1-way quantum automata. In <em>Proceedings of the thirty-first annual ACM symposium on Theory of computing</em>, 376–383. 1999. <a href="https://doi.org/https://doi.org/10.1145/301250.301347">https://doi.org/https://doi.org/10.1145/301250.301347</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Ambainis%2C+Andris%2C+Nayak%2C+Ashwin%2C+Ta-Shma%2C+Ammon%2C+and+%0AVazirani%2C+Umesh+Dense+quantum+coding+and+a+lower+bound+for+1-way+quantum+automata+1999" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Ambainis%2C+Andris%2C+Nayak%2C+Ashwin%2C+Ta-Shma%2C+Ammon%2C+and+%0AVazirani%2C+Umesh&title=Dense+quantum+coding+and+a+lower+bound+for+1-way+quantum+automata&submittedafter=1998&submittedbefore=2000" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[BBBV97]</div> <div>Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. <em>SIAM journal on Computing</em>, 26(5):1510–1523, 1997. <a href="https://doi.org/https://doi.org/10.1137/S0097539796300933">https://doi.org/https://doi.org/10.1137/S0097539796300933</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Bennett%2C+Charles+H%2C+Bernstein%2C+Ethan%2C+Brassard%2C+Gilles%2C+and+%0AVazirani%2C+Umesh+Strengths+and+weaknesses+of+quantum+computing+1997" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Bennett%2C+Charles+H%2C+Bernstein%2C+Ethan%2C+Brassard%2C+Gilles%2C+and+%0AVazirani%2C+Umesh&title=Strengths+and+weaknesses+of+quantum+computing&submittedafter=1996&submittedbefore=1998" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[BY23]</div> <div>Aleksandrs Belovs and Duyal Yolcu. One-way ticket to las vegas and the quantum adversary. <em>arXiv preprint arXiv:2301.02003</em>, 2023. <a href="https://doi.org/https://doi.org/10.48550/arXiv.2301.02003">https://doi.org/https://doi.org/10.48550/arXiv.2301.02003</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Belovs%2C+Aleksandrs+and+Yolcu%2C+Duyal+One-Way+Ticket+to+Las+Vegas+and+the+Quantum+Adversary+2023" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Belovs%2C+Aleksandrs+and+Yolcu%2C+Duyal&title=One-Way+Ticket+to+Las+Vegas+and+the+Quantum+Adversary&submittedafter=2022&submittedbefore=2024" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[CGBH<sup>+</sup>18]</div> <div>Jan Czajkowski, Leon Groot Bruinderink, Andreas H<span class="bibtex-protected">ü</span>lsing, Christian Schaffner, and Dominique Unruh. Post-quantum security of the sponge construction. In <em>International Conference on Post-Quantum Cryptography</em>, 185–204. Springer, 2018. <a href="https://doi.org/https://doi.org/10.1007/978-3-319-79063-3_9">https://doi.org/https://doi.org/10.1007/978-3-319-79063-3_9</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Czajkowski%2C+Jan%2C+Groot+Bruinderink%2C+Leon%2C+H%C3%BClsing%2C+Andreas%2C+Schaffner%2C+Christian%2C+and+%0AUnruh%2C+Dominique+Post-quantum+security+of+the+sponge+construction+2018" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Czajkowski%2C+Jan%2C+Groot+Bruinderink%2C+Leon%2C+H%C3%BClsing%2C+Andreas%2C+Schaffner%2C+Christian%2C+and+%0AUnruh%2C+Dominique&title=Post-quantum+security+of+the+sponge+construction&submittedafter=2017&submittedbefore=2019" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[CGLQ20]</div> <div>Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian. Tight quantum time-space tradeoffs for function inversion. In <em>2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)</em>, 673–684. IEEE, 2020. <a href="https://doi.org/10.1109/FOCS46700.2020.00068">https://doi.org/10.1109/FOCS46700.2020.00068</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Chung%2C+Kai-Min%2C+Guo%2C+Siyao%2C+Liu%2C+Qipeng%2C+and+%0AQian%2C+Luowen+Tight+quantum+time-space+tradeoffs+for+function+inversion+2020" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Chung%2C+Kai-Min%2C+Guo%2C+Siyao%2C+Liu%2C+Qipeng%2C+and+%0AQian%2C+Luowen&title=Tight+quantum+time-space+tradeoffs+for+function+inversion&submittedafter=2019&submittedbefore=2021" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[CLQ19]</div> <div>Kai-Min Chung, Tai-Ning Liao, and Luowen Qian. Lower bounds for function inversion with quantum advice. <em>arXiv preprint arXiv:1911.09176</em>, 2019. <a href="https://doi.org/https://doi.org/10.48550/arXiv.1911.09176">https://doi.org/https://doi.org/10.48550/arXiv.1911.09176</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Chung%2C+Kai-Min%2C+Liao%2C+Tai-Ning%2C+and+%0AQian%2C+Luowen+Lower+bounds+for+function+inversion+with+quantum+advice+2019" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Chung%2C+Kai-Min%2C+Liao%2C+Tai-Ning%2C+and+%0AQian%2C+Luowen&title=Lower+bounds+for+function+inversion+with+quantum+advice&submittedafter=2018&submittedbefore=2020" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[CMSZ21]</div> <div>Jan Czajkowski, Christian Majenz, Christian Schaffner, and Sebastian Zur. Quantum lazy sampling and game-playing proofs for quantum indifferentiability. <em>arXiv preprint arXiv:1904.11477</em>, 2021. <a href="https://doi.org/https://doi.org/10.48550/arXiv.1904.11477">https://doi.org/https://doi.org/10.48550/arXiv.1904.11477</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Czajkowski%2C+Jan%2C+Majenz%2C+Christian%2C+Schaffner%2C+Christian%2C+and+%0AZur%2C+Sebastian+Quantum+lazy+sampling+and+game-playing+proofs+for+quantum+indifferentiability+2021" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Czajkowski%2C+Jan%2C+Majenz%2C+Christian%2C+Schaffner%2C+Christian%2C+and+%0AZur%2C+Sebastian&title=Quantum+lazy+sampling+and+game-playing+proofs+for+quantum+indifferentiability&submittedafter=2020&submittedbefore=2022" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[CX21]</div> <div>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. <em>Theoretical Computer Science</em>, 855:16–42, 2021. <a href="https://doi.org/https://doi.org/10.1016/j.tcs.2020.11.013">https://doi.org/https://doi.org/10.1016/j.tcs.2020.11.013</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Cao%2C+Shujiao+and+Xue%2C+Rui+Being+a+permutation+is+also+orthogonal+to+one-wayness+in+quantum+world%3A+Impossibilities+of+quantum+one-way+permutations+from+one-wayness+primitives+2021" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Cao%2C+Shujiao+and+Xue%2C+Rui&title=Being+a+permutation+is+also+orthogonal+to+one-wayness+in+quantum+world%3A+Impossibilities+of+quantum+one-way+permutations+from+one-wayness+primitives&submittedafter=2020&submittedbefore=2022" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[DH08]</div> <div>Catalin Dohotaru and Peter Hoyer. Exact quantum lower bound for grover's problem. <em>arXiv preprint arXiv:0810.3647</em>, 2008. <a href="https://doi.org/https://doi.org/10.26421/QIC9.5-6-12">https://doi.org/https://doi.org/10.26421/QIC9.5-6-12</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Dohotaru%2C+Catalin+and+Hoyer%2C+Peter+Exact+quantum+lower+bound+for+Grover%27s+problem+2008" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Dohotaru%2C+Catalin+and+Hoyer%2C+Peter&title=Exact+quantum+lower+bound+for+Grover%27s+problem&submittedafter=2007&submittedbefore=2009" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[DKRS23]</div> <div>Orr Dunkelman, Nathan Keller, Eyal Ronen, and Adi Shamir. Quantum time/memory/data tradeoff attacks. <em>Designs, Codes and Cryptography</em>, pages 1–19, 2023. <a href="https://doi.org/https://doi.org/10.1007/s10623-023-01300-x">https://doi.org/https://doi.org/10.1007/s10623-023-01300-x</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Dunkelman%2C+Orr%2C+Keller%2C+Nathan%2C+Ronen%2C+Eyal%2C+and+%0AShamir%2C+Adi+Quantum+time%2Fmemory%2Fdata+tradeoff+attacks+2023" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Dunkelman%2C+Orr%2C+Keller%2C+Nathan%2C+Ronen%2C+Eyal%2C+and+%0AShamir%2C+Adi&title=Quantum+time%2Fmemory%2Fdata+tradeoff+attacks&submittedafter=2022&submittedbefore=2024" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Dwo15]</div> <div>Morris J Dworkin. Sha-3 standard: permutation-based hash and extendable-output functions. <em>Federal Inf. Process. Stds. (NIST FIPS)</em>, 2015. <a href="https://doi.org/https://doi.org/10.6028/NIST.FIPS.202">https://doi.org/https://doi.org/10.6028/NIST.FIPS.202</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Dworkin%2C+Morris+J+SHA-3+standard%3A+Permutation-based+hash+and+extendable-output+functions+2015" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Dworkin%2C+Morris+J&title=SHA-3+standard%3A+Permutation-based+hash+and+extendable-output+functions&submittedafter=2014&submittedbefore=2016" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[FK15]</div> <div>Bill Fefferman and Shelby Kimmel. Quantum vs classical proofs and subset verification. <em>arXiv preprint arXiv:1510.06750</em>, 2015. <a href="https://doi.org/https://doi.org/10.48550/arXiv.1510.06750">https://doi.org/https://doi.org/10.48550/arXiv.1510.06750</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Fefferman%2C+Bill+and+Kimmel%2C+Shelby+Quantum+vs+classical+proofs+and+subset+verification+2015" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Fefferman%2C+Bill+and+Kimmel%2C+Shelby&title=Quantum+vs+classical+proofs+and+subset+verification&submittedafter=2014&submittedbefore=2016" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[GJMG11]</div> <div>Bertoni Guido, Daemen Joan, P Micha<span class="bibtex-protected">ë</span>l, and VA Gilles. <a href="https://keccak.team/files/CSF-0.1.pdf">Cryptographic sponge functions.</a> 2011.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Guido%2C+Bertoni%2C+Joan%2C+Daemen%2C+Micha%C3%ABl%2C+P%2C+and+%0AGilles%2C+VA+Cryptographic+sponge+functions+2011" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Guido%2C+Bertoni%2C+Joan%2C+Daemen%2C+Micha%C3%ABl%2C+P%2C+and+%0AGilles%2C+VA&title=Cryptographic+sponge+functions&submittedafter=2010&submittedbefore=2012" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Gro96]</div> <div>Lov K Grover. A fast quantum mechanical algorithm for database search. In <em>Proceedings of the twenty-eighth annual ACM symposium on Theory of computing</em>, 212–219. 1996. <a href="https://doi.org/https://doi.org/10.1145/237814.237866">https://doi.org/https://doi.org/10.1145/237814.237866</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Grover%2C+Lov+K+A+fast+quantum+mechanical+algorithm+for+database+search+1996" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Grover%2C+Lov+K&title=A+fast+quantum+mechanical+algorithm+for+database+search&submittedafter=1995&submittedbefore=1997" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[HXY19]</div> <div>Minki Hhan, Keita Xagawa, and Takashi Yamakawa. Quantum random oracle model with auxiliary input. In <em>International Conference on the Theory and Application of Cryptology and Information Security</em>, 584–614. Springer, 2019. <a href="https://doi.org/https://doi.org/10.1007/978-3-030-34578-5_21">https://doi.org/https://doi.org/10.1007/978-3-030-34578-5_21</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Hhan%2C+Minki%2C+Xagawa%2C+Keita%2C+and+%0AYamakawa%2C+Takashi+Quantum+random+oracle+model+with+auxiliary+input+2019" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Hhan%2C+Minki%2C+Xagawa%2C+Keita%2C+and+%0AYamakawa%2C+Takashi&title=Quantum+random+oracle+model+with+auxiliary+input&submittedafter=2018&submittedbefore=2020" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[KL20]</div> <div>Jonathan Katz and Yehuda Lindell. <em>Introduction to modern cryptography</em>. CRC press, 2020. <a href="https://doi.org/https://doi.org/10.1201/9781420010756">https://doi.org/https://doi.org/10.1201/9781420010756</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Katz%2C+Jonathan+and+Lindell%2C+Yehuda+Introduction+to+modern+cryptography+2020" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Katz%2C+Jonathan+and+Lindell%2C+Yehuda&title=Introduction+to+modern+cryptography&submittedafter=2019&submittedbefore=2021" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Liu23]</div> <div>Qipeng Liu. Non-uniformity and quantum advice in the quantum random oracle model. In <em>Annual International Conference on the Theory and Applications of Cryptographic Techniques</em>, 117–143. Springer, 2023. <a href="https://doi.org/https://doi.org/10.1007/978-3-031-30545-0_5">https://doi.org/https://doi.org/10.1007/978-3-031-30545-0_5</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Liu%2C+Qipeng+Non-uniformity+and+Quantum+Advice+in+the+Quantum+Random+Oracle+Model+2023" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Liu%2C+Qipeng&title=Non-uniformity+and+Quantum+Advice+in+the+Quantum+Random+Oracle+Model&submittedafter=2022&submittedbefore=2024" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[NABT14]</div> <div>Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan. Quantum lower bound for inverting a permutation with advice. <em>arXiv preprint arXiv:1408.3193</em>, 2014. <a href="https://doi.org/https://doi.org/10.48550/arXiv.1408.3193">https://doi.org/https://doi.org/10.48550/arXiv.1408.3193</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Nayebi%2C+Aran%2C+Aaronson%2C+Scott%2C+Belovs%2C+Aleksandrs%2C+and+%0ATrevisan%2C+Luca+Quantum+lower+bound+for+inverting+a+permutation+with+advice+2014" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Nayebi%2C+Aran%2C+Aaronson%2C+Scott%2C+Belovs%2C+Aleksandrs%2C+and+%0ATrevisan%2C+Luca&title=Quantum+lower+bound+for+inverting+a+permutation+with+advice&submittedafter=2013&submittedbefore=2015" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Nay10]</div> <div>Ashwin Nayak. Inverting a permutation is as hard as unordered search. <em>arXiv preprint arXiv:1007.2899</em>, 2010. <a href="https://doi.org/https://doi.org/10.48550/arXiv.1007.2899">https://doi.org/https://doi.org/10.48550/arXiv.1007.2899</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Nayak%2C+Ashwin+Inverting+a+permutation+is+as+hard+as+unordered+search+2010" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Nayak%2C+Ashwin&title=Inverting+a+permutation+is+as+hard+as+unordered+search&submittedafter=2009&submittedbefore=2011" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Reg09]</div> <div>Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. <em>Journal of the ACM (JACM)</em>, 56(6):1–40, 2009. <a href="https://doi.org/https://doi.org/10.1145/1568318.1568324">https://doi.org/https://doi.org/10.1145/1568318.1568324</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Regev%2C+Oded+On+lattices%2C+learning+with+errors%2C+random+linear+codes%2C+and+cryptography+2009" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Regev%2C+Oded&title=On+lattices%2C+learning+with+errors%2C+random+linear+codes%2C+and+cryptography&submittedafter=2008&submittedbefore=2010" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Ros21]</div> <div>Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments. <em>arXiv preprint arXiv:2103.08975</em>, 2021. <a href="https://doi.org/https://doi.org/10.48550/arXiv.2103.08975">https://doi.org/https://doi.org/10.48550/arXiv.2103.08975</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Rosmanis%2C+Ansis+Tight+bounds+for+inverting+permutations+via+compressed+oracle+arguments+2021" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Rosmanis%2C+Ansis&title=Tight+bounds+for+inverting+permutations+via+compressed+oracle+arguments&submittedafter=2020&submittedbefore=2022" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Vaz98]</div> <div>Umesh Vazirani. On the power of quantum computation. <em>Philosophical Transactions of the Royal Society of London A 365: 1759-1768</em>, 1998. <a href="https://doi.org/https://doi.org/10.1137/S0097539796298637">https://doi.org/https://doi.org/10.1137/S0097539796298637</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Vazirani%2C+Umesh+On+the+power+of+quantum+computation+1998" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Vazirani%2C+Umesh&title=On+the+power+of+quantum+computation&submittedafter=1997&submittedbefore=1999" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Wie83]</div> <div>Stephen Wiesner. Conjugate coding. <em>ACM Sigact News</em>, 15(1):78–88, 1983. <a href="https://doi.org/https://doi.org/10.1145/1008908.1008920">https://doi.org/https://doi.org/10.1145/1008908.1008920</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Wiesner%2C+Stephen+Conjugate+coding+1983" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Wiesner%2C+Stephen&title=Conjugate+coding&submittedafter=1982&submittedbefore=1984" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Zal99]</div> <div>Christof Zalka. Grover’s quantum searching algorithm is optimal. <em>Physical Review A</em>, 60(4):2746, 1999. <a href="https://doi.org/https://doi.org/10.1103/PhysRevA.60.2746">https://doi.org/https://doi.org/10.1103/PhysRevA.60.2746</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Zalka%2C+Christof+Grover%E2%80%99s+quantum+searching+algorithm+is+optimal+1999" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Zalka%2C+Christof&title=Grover%E2%80%99s+quantum+searching+algorithm+is+optimal&submittedafter=1998&submittedbefore=2000" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Zha16]</div> <div>Mark Zhandry. A note on quantum-secure prps. <em>arXiv preprint arXiv:1611.05564</em>, 2016. <a href="https://doi.org/https://doi.org/10.48550/arXiv.1611.05564">https://doi.org/https://doi.org/10.48550/arXiv.1611.05564</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Zhandry%2C+Mark+A+note+on+quantum-secure+PRPs+2016" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Zhandry%2C+Mark&title=A+note+on+quantum-secure+PRPs&submittedafter=2015&submittedbefore=2017" target="_blank" class="ms-3">ePrint</a> </div> <div class="d-flex"> <div style="min-width:9rem;">[Zha19]</div> <div>Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In <em>Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part II 39</em>, 239–268. Springer, 2019. <a href="https://doi.org/https://doi.org/10.1007/978-3-030-26951-7_9">https://doi.org/https://doi.org/10.1007/978-3-030-26951-7_9</a>.</div> </div> <div class="text-end mb-4"> <a href="https://scholar.google.com/scholar?hl=en&q=Zhandry%2C+Mark+How+to+record+quantum+queries%2C+and+applications+to+quantum+indifferentiability+2019" target="_blank" class="ms-3">Google Scholar</a> <a href="https://eprint.iacr.org/search?relevance=on&authors=Zhandry%2C+Mark&title=How+to+record+quantum+queries%2C+and+applications+to+quantum+indifferentiability&submittedafter=2018&submittedbefore=2020" target="_blank" class="ms-3">ePrint</a> </div> </div> <div class="col-12 col-md-4"> <p class="mt-4"> <a class="btn btn-outline-dark" href="/p/1/1/27/pdf"><img alt="PDF" class="icon" src="/images/file-pdf.svg">PDF</a> <img style="margin-left: 1rem;max-width: 1.2rem;" src="/images/open_access.svg" title="Open access" alt="Open access"> </p> <div class="my-4"> <span class="fw-bold me-2">DOI:</span> <a href="https://doi.org/10.62056/a0qj89n4e">https://doi.org/10.62056/a0qj89n4e</a> </div> <div class="card mb-4"> <h5 class="card-header">History</h5> <div class="card-body"> <strong>Submitted</strong>: 2024-01-09<br> <strong>Accepted</strong>: 2024-03-05<br> <strong>Published</strong>: 2024-04-09<br> <!-- begin crossmark --> <script src="https://crossmark-cdn.crossref.org/widget/v2.0/widget.js"></script> <a data-target="crossmark"><img style="margin-top:4px;" src="https://crossmark-cdn.crossref.org/widget/v2.0/logos/CROSSMARK_Color_horizontal.svg" width="150" /></a> <!-- end crossmark --> </div> </div> <div class="card mb-4"> <h5 class="card-header">How to cite</h5> <div class="card-body"> <p>Gorjan Alagic, Chen Bai, Alexander Poremba, and Kaiyan Shi, On the Two-sided Permutation Inversion Problem. <span class="fst-italic">IACR Communications in Cryptology</span>, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a0qj89n4e. </p> <button type="button" id="citationModalLabel" class="float-end btn btn-outline-dark" data-bs-toggle="modal" data-bs-target="#citationModal"> BibTeX, etc </button> </div> </div> <div class="card mb-4"> <h5 class="card-header">Citations</h5> <div class="card-body"> <p>There is at least one citation.</p> <button type="button" id="citationsModalLabel" class="float-end btn btn-outline-dark" data-bs-toggle="modal" data-bs-target="#citationsModal">Show citations</button> </div> </div> <div class="card mb-4"> <h5 class="card-header">License</h5> <div class="card-body"> <p>Copyright is held by the author(s)</p> <p> This work is licensed under a <a target="_blank" href="https://creativecommons.org/licenses/by/4.0/">Creative Commons Attribution (CC BY)</a> license. </p> </div> </div> </div> </div> <div class="modal fade" id="citationModal" tabindex="-1" aria-labelledby="citationModalLabel" aria-hidden="true"> <div class="modal-dialog modal-xl"> <div class="modal-content"> <div class="modal-header"> <h1 class="modal-title fs-3">How to cite this</h1> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body p-4"> <ul class="nav nav-tabs" id="myTab" role="tablist"> <li class="nav-item" role="presentation"> <button class="nav-link active" id="bibtex-tab" data-bs-toggle="tab" data-bs-target="#bibtex-pane" type="button" role="tab" aria-controls="bibtex-pane" aria-selected="true">BibTeX</button> </li> <li class="nav-item" role="presentation"> <button class="nav-link" id="ris-tab" data-bs-toggle="tab" data-bs-target="#ris-pane" type="button" role="tab" aria-controls="ris-pane" aria-selected="false">RIS/Endnote/Zotero/Mendeley</button> </li> <li class="nav-item" role="presentation"> <button class="nav-link" id="text-tab" data-bs-toggle="tab" data-bs-target="#text-pane" type="button" role="tab" aria-controls="text-pane" aria-selected="false">Text</button> </li> </ul> <div class="tab-content p-4"> <div class="tab-pane active" id="bibtex-pane" role="tabpanel" aria-labelledby="bibtex-tab" tabindex="0"> <pre id="bib">@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" } </pre> <button id="bibtexcopy" class="btn btn-sm btn-primary" aria-label="Copy to clipboard" onclick="copyMetadata('bibtexcopy', 'bib')">Copy to clipboard</button> <button id="bibtexdownload" class="ms-3 btn btn-sm btn-primary" aria-label="Download BibTeX .bib file" onclick="sendCitation('bib')">Download .bib file</button> </div> <div class="tab-pane" id="ris-pane" role="tabpanel" aria-labelledby="ris-tab" tabindex="0"> <pre id="ris">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 -</pre> <button id="riscopy" class="btn btn-sm btn-primary" aria-label="Copy to clipboard" onclick="copyMetadata('riscopy', 'ris')">Copy to clipboard</button> <button id="risdownload" class="ms-3 btn btn-sm btn-primary" aria-label="Download RIS file" onclick="sendCitation('ris')">Download .ris file</button> </div> <div class="tab-pane" id="text-pane" role="tabpanel" aria-labelledby="text-tab" tabindex="0"> <div class="w-75" id="textcitation">Gorjan Alagic, Chen Bai, Alexander Poremba, and Kaiyan Shi, On the Two-sided Permutation Inversion Problem. <span class="fst-italic">IACR Communications in Cryptology</span>, vol. 1, no. 1, Apr 09, 2024, doi: 10.62056/a0qj89n4e.</div> <button id="textcopy" class="btn btn-sm btn-primary mt-3" aria-label="Copy to clipboard" onclick="copyMetadata('textcopy', 'textcitation')">Copy to clipboard</button> </div> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> </div> </div> </div> </div> <div class="modal fade" id="citationsModal" tabindex="-1" aria-labelledby="citationsModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-scrollable modal-lg"> <div class="modal-content"> <div class="modal-header"> <h1 class="modal-title fs-3">Known citations</h1> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body p-4"> <p> We do not crawl the web, so we are only able to identify citations from papers that are registered with a DOI in crossref.org and the publisher reports their citations to crossref, and crossref can identify a DOI from the reference. That includes (most) articles from Springer and many from ACM, but it excludes citations from USENIX because they don't issue DOIs. It also excludes citations from arxiv and eprint. You may find more citations in <a href="https://scholar.google.com/scholar?hl=en&q=On+the+Two-sided+Permutation+Inversion+Problem">Google Scholar</a>. </p> <ol> <li>Joseph Carolan and Alexander Poremba. Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations. <em>Advances in Cryptology – CRYPTO 2024</em> Lecture Notes in Computer Science Volume 14925 (2024), p. 218 DOI: <a href="https://doi.org/10.1007/978-3-031-68391-6_7" target="_blank">10.1007/978-3-031-68391-6_7</a></li> </ol> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> </div> </div> </div> </div> <script> function copyMetadata(buttid, id) { let range = document.createRange(); range.selectNode(document.getElementById(id)); window.getSelection().removeAllRanges(); window.getSelection().addRange(range); document.execCommand('copy'); window.getSelection().removeAllRanges(); const copyTooltip = new bootstrap.Tooltip('#' + buttid, {trigger: 'manual', title: 'Copied!'}); copyTooltip.show(); setTimeout(function() { copyTooltip.dispose(); }, 2000); } function sendCitation(typ) { // typ is 'bib' or 'ris' let data = document.getElementById(typ).innerHTML; atag = document.createElement('a'); atag.setAttribute('href', 'data:text/plain;charset=utf-8,' + encodeURIComponent(data)); atag.setAttribute('download', '1-1-27.' + typ); if (document.createEvent) { let event = document.createEvent('MouseEvents'); event.initEvent('click', true, true); atag.dispatchEvent(event); } else { atag.click(); } } </script> </main> <div class="container-fluid mt-auto" id="pageFooter"> </div> <footer class="text-center footer py-3"> <small> <a href="https://iacr.org/copyright.html">Copyright © 2025</a> <span class="d-none d-md-inline">by the </span><span class="d-md-none">IACR</span> <span class="d-none d-md-inline">International Association for Cryptologic Research</span> <span class="d-none d-md-inline">• </span><br class="d-md-none"> <a href="https://iacr.org/privacy.html">Privacy Policy</a> </small> </footer> <script id="results-template" type="text/x-handlebars-template"> <div class="p-3 shadow" style="margin-bottom:1rem;max-height:70vh;overflow-y:scroll"> <p>{{estimated_results}} results (if more than 100, then refine your query)</p> <ol> {{#each results}} <li role="presentation"><a href="{{url}}">{{title}}</a><br> {{#each authors }}{{this}}{{#unless @last}}, {{/unless}}{{/each}}</li> {{/each}} </ol> </div> </script> <script src="/static/js/handlebars-v4.7.7.js"></script> <script> var theTemplateScript = document.getElementById('results-template').innerHTML; var resultsTemplate = Handlebars.compile(theTemplateScript); var textinput = document.getElementById('searchbox'); // Returns a function, that, as long as it continues to be invoked, will not // be triggered. The function will be called after it stops being called for // N milliseconds. If `immediate` is passed, trigger the function on the // leading edge, instead of the trailing. function debounce(func, wait, immediate) { var timeout; return function() { var context = this, args = arguments; var later = function() { timeout = null; if (!immediate) func.apply(context, args); }; var callNow = immediate && !timeout; clearTimeout(timeout); timeout = setTimeout(later, wait); if (callNow) func.apply(context, args); }; }; let controller; let signal; var doSearch = debounce(function() { args = {'d': '/var/www/wsgi/cicjournal/webapp/search_index/xapian.db'} if (textinput.value) { args['q'] = textinput.value; if (controller !== undefined) { console.log('killing'); controller.abort(); } controller = new AbortController(); signal = controller.signal; let search_url = "https://cic.iacr.org/api/search" + "?" + new URLSearchParams(args); console.log(search_url); fetch(search_url, {signal}) .then((response) => response.json()) .then((data) => { console.log(data); let elem = document.getElementById('view'); if (elem) {elem.innerHTML = '';} if (data.results.length > 0) { document.getElementById('results').innerHTML = resultsTemplate(data); } else { document.getElementById('results').innerHTML = '<div class="p-3 shadow">no results</div>'; } controller = undefined; }).catch((error) => { console.log('error in fetch'); console.log(error); }); } else { console.log('no query'); } }, 500); // only after 250 ms. document.querySelectorAll('input').forEach((elem) => { elem.addEventListener('input', doSearch); }); </script> </body> </html>