{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T14:25:57Z","timestamp":1781533557579,"version":"3.54.5"},"reference-count":35,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-18-CE39-0007"],"award-info":[{"award-number":["ANR-18-CE39-0007"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-PETQ-0008 PQ-TLS"],"award-info":[{"award-number":["ANR-22-PETQ-0008 PQ-TLS"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["740972"],"award-info":[{"award-number":["740972"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,9,2]]},"abstract":"<jats:p>In this paper we study search problems that arise very often in cryptanalysis: nested search problems, where each search layer has known degrees of freedom and\/or constraints. A generic quantum solution for such problems consists of nesting Grover's quantum search algorithm or amplitude amplification (QAA) by Brassard et al., obtaining up to a square-root speedup on classical algorithms. However, the analysis of nested Grover or QAA is complex and introduces technicalities that in previous works are handled in a case-by-case manner. Moreover, straightforward nesting of l layers multiplies the complexity by a constant factor (pi\/2)^l.<\/jats:p>\n                  <jats:p>In this paper, we aim to remedy both these issues and introduce a generic framework and tools to transform a classical nested search into a quantum procedure. It improves the state-of-the-art in three ways: 1) our framework results in quantum procedures that are significantly simpler to describe and analyze; 2) it reduces the overhead factor from (pi\/2)^l to sqrt(l); 3) it is simpler to apply and optimize, without needing manual quantum analysis. We give generic complexity formulas and show that for concrete instances, numerical optimizations enable further improvements, reducing even more the gap to an exact quadratic speedup.<\/jats:p>\n                  <jats:p>We demonstrate our framework by giving a tighter analysis of quantum attacks on reduced-round AES.<\/jats:p>","DOI":"10.62056\/aee0fhbmo","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T11:13:33Z","timestamp":1728299613000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["Quantum Procedures for Nested Search Problems"],"prefix":"10.62056","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1329-8630","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schrottenloher","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04040yw90","id-type":"ROR","asserted-by":"publisher"}],"name":"Univ Rennes, Inria, CNRS, IRISA","place":["Rennes, 35000, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7091-2924","authenticated-orcid":false,"given":"Marc","family":"Stevens","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/00x7ekv49","id-type":"ROR","asserted-by":"publisher"}],"name":"CWI","place":["Amsterdam, The Netherlands"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"ref1:DBLP:conf\/focs\/Shor94","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","article-title":"Algorithms for Quantum Computation: Discrete Logarithms and\n  Factoring","author":"Peter W. Shor","year":"1994"},{"key":"ref2:alagic2022status","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.IR.8413-upd1","article-title":"Status report on the third round of the NIST post-quantum\n  cryptography standardization process","author":"Gorjan Alagic","year":"2022","journal-title":"US Department of Commerce, NIST"},{"key":"ref3:DBLP:conf\/stoc\/Grover96","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/237814.237866","article-title":"A Fast Quantum Mechanical Algorithm for Database Search","author":"Lov K. Grover","year":"1996"},{"key":"ref4:brassard2002quantum","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","article-title":"Quantum amplitude amplification and estimation","volume":"305","author":"Gilles Brassard","year":"2002","journal-title":"Contemporary Mathematics"},{"key":"ref5:DBLP:conf\/pqcrypto\/Bernstein10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/978-3-642-12929-2_6","article-title":"Grover vs. McEliece","volume":"6061","author":"Daniel J. Bernstein","year":"2010"},{"key":"ref6:DBLP:conf\/pqcrypto\/KachigarT17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-319-59879-6_5","article-title":"Quantum Information Set Decoding Algorithms","volume":"10346","author":"Ghazal Kachigar","year":"2017"},{"key":"ref7:DBLP:journals\/dcc\/LaarhovenMP15","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10623-015-0067-5","article-title":"Finding shortest lattice vectors faster using quantum\n  search","volume":"77","author":"Thijs Laarhoven","year":"2015","journal-title":"Des. Codes Cryptogr."},{"key":"ref8:laarhoven2015search","volume-title":"Search problems in cryptography","author":"Thijs Laarhoven","year":"2015"},{"key":"ref9:DBLP:conf\/asiacrypt\/KirshanovaMPM19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/978-3-030-34578-5_19","article-title":"Quantum Algorithms for the Approximate k-List Problem and\n  Their Application to Lattice Sieving","volume":"11921","author":"Elena Kirshanova","year":"2019"},{"key":"ref10:DBLP:conf\/isit\/KuwakadoM10","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1109\/ISIT.2010.5513654","article-title":"Quantum distinguisher between the 3-round Feistel cipher and\n  the random permutation","author":"Hidenori Kuwakado","year":"2010"},{"key":"ref11:DBLP:conf\/crypto\/KaplanLLN16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-662-53008-5_8","article-title":"Breaking Symmetric Cryptosystems Using Quantum Period\n  Finding","volume":"9815","author":"Marc Kaplan","year":"2016"},{"key":"ref12:DBLP:journals\/tosc\/KaplanLLN16","doi-asserted-by":"publisher","first-page":"71","DOI":"10.13154\/TOSC.V2016.I1.71-94","article-title":"Quantum Differential and Linear Cryptanalysis","volume":"2016","author":"Marc Kaplan","year":"2016","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref13:DBLP:conf\/eurocrypt\/HosoyamadaS20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-030-45724-2_9","article-title":"Finding Hash Collisions with Quantum Computers by Using\n  Differential Trails with Smaller Probability than Birthday Bound","volume":"12106","author":"Akinori Hosoyamada","year":"2020"},{"key":"ref14:cryptoeprint:2022\/754","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/S10623-023-01280-Y","volume-title":"Quantum impossible differential attacks: applications to\n  AES and SKINNY","volume":"92","author":"Nicolas David","year":"2024","journal-title":"Des. Codes Cryptogr."},{"key":"ref15:DBLP:journals\/tosc\/BonnetainNS19","doi-asserted-by":"publisher","first-page":"55","DOI":"10.13154\/TOSC.V2019.I2.55-93","article-title":"Quantum Security Analysis of AES","volume":"2019","author":"Xavier Bonnetain","year":"2019","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref16:DBLP:conf\/sacrypt\/DavenportP20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-030-81652-0_14","article-title":"Improvements to Quantum Search Techniques for Block-Ciphers,\n  with Applications to AES","volume":"12804","author":"James H. Davenport","year":"2020"},{"key":"ref17:DBLP:conf\/tqc\/KimmelLL15","series-title":"LIPIcs","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4230\/LIPICS.TQC.2015.1","article-title":"Oracles with Costs","volume":"44","author":"Shelby Kimmel","year":"2015"},{"key":"ref18:DBLP:journals\/toc\/Montanaro18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/TOC.2018.V014A015","article-title":"Quantum-Walk Speedup of Backtracking Algorithms","volume":"14","author":"Ashley Montanaro","year":"2018","journal-title":"Theory Comput."},{"key":"ref19:DBLP:conf\/asiacrypt\/AonoNS18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-030-03326-2_14","article-title":"Quantum Lattice Enumeration and Tweaking Discrete Pruning","volume":"11272","author":"Yoshinori Aono","year":"2018"},{"key":"ref20:DBLP:journals\/mst\/Ambainis10","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1007\/S00224-009-9219-1","article-title":"Quantum Search with Variable Times","volume":"47","author":"Andris Ambainis","year":"2010","journal-title":"Theory Comput. Syst."},{"key":"ref21:DBLP:conf\/stacs\/Ambainis12","series-title":"LIPIcs","doi-asserted-by":"publisher","first-page":"636","DOI":"10.4230\/LIPICS.STACS.2012.636","article-title":"Variable time amplitude amplification and quantum algorithms\n  for linear algebra problems","volume":"14","author":"Andris Ambainis","year":"2012"},{"key":"ref22:ambainis2023improved","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.TQC.2023.7","volume-title":"TQC","volume":"266","author":"Andris Ambainis","year":"2023"},{"key":"ref23:nielsen2002quantum","isbn-type":"print","volume-title":"Quantum Computation and Quantum Information (10th\n  Anniversary edition)","author":"Michael A. Nielsen","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9781107002173"},{"key":"ref24:DBLP:conf\/tqc\/Kuperberg13","series-title":"LIPIcs","doi-asserted-by":"publisher","first-page":"20","DOI":"10.4230\/LIPICS.TQC.2013.20","article-title":"Another Subexponential-time Quantum Algorithm for the\n  Dihedral Hidden Subgroup Problem","volume":"22","author":"Greg Kuperberg","year":"2013"},{"key":"ref25:gidneyblog","volume-title":"Constructing Large Controlled Nots","author":"Craig Gidney","year":"2015"},{"key":"ref26:DBLP:journals\/toc\/AaronsonA05","doi-asserted-by":"publisher","first-page":"47","DOI":"10.4086\/TOC.2005.V001A004","article-title":"Quantum Search of Spatial Regions","volume":"1","author":"Scott Aaronson","year":"2005","journal-title":"Theory Comput."},{"key":"ref27:DBLP:conf\/asiacrypt\/BonnetainHNSS19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1007\/978-3-030-34578-5_20","article-title":"Quantum Attacks Without Superposition Queries: The Offline\n  Simon's Algorithm","volume":"11921","author":"Xavier Bonnetain","year":"2019"},{"key":"ref28:DBLP:conf\/eurocrypt\/JaquesNRV20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-030-45724-2_10","article-title":"Implementing Grover Oracles for Quantum Key Search on AES\n  and LowMC","volume":"12106","author":"Samuel Jaques","year":"2020"},{"key":"ref29:DBLP:books\/sp\/DaemenR02","series-title":"Information Security and Cryptography","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04722-4","volume-title":"The Design of Rijndael: AES - The Advanced Encryption\n  Standard","author":"Joan Daemen","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/3540425802"},{"key":"ref30:DBLP:conf\/fse\/FergusonKLSSWW00","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/3-540-44706-7_15","article-title":"Improved Cryptanalysis of Rijndael","volume":"1978","author":"Niels Ferguson","year":"2000"},{"key":"ref31:knudsen1998deal","volume-title":"DEAL - a 128-bit block cipher","author":"Lars Knudsen","year":"1998"},{"key":"ref32:DBLP:journals\/joc\/BihamBS05","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/S00145-005-0129-3","article-title":"Cryptanalysis of Skipjack Reduced to 31 Rounds Using\n  Impossible Differentials","volume":"18","author":"Eli Biham","year":"2005","journal-title":"J. Cryptol."},{"key":"ref33:DBLP:conf\/indocrypt\/MalaDRM10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/978-3-642-17401-8_20","article-title":"Improved Impossible Differential Cryptanalysis of 7-Round\n  AES-128","volume":"6498","author":"Hamid Mala","year":"2010"},{"key":"ref34:DBLP:conf\/eurocrypt\/DerbezFJ13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-38348-9_23","article-title":"Improved Key Recovery Attacks on Reduced-Round AES in the\n  Single-Key Setting","volume":"7881","author":"Patrick Derbez","year":"2013"},{"key":"ref35:DBLP:conf\/icalp\/ChakrabortyGJ19","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2019.33","article-title":"The Power of Block-Encoded Matrix Powers: Improved\n  Regression Techniques via Faster Hamiltonian Simulation","volume":"132","author":"Shantanav Chakraborty","year":"2019"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T16:28:11Z","timestamp":1733848091000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/3\/9"}},"subtitle":["with Applications in Cryptanalysis"],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":35,"URL":"https:\/\/doi.org\/10.62056\/aee0fhbmo","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"2024-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-3-27"}}