Paper 2022/761

A Quantum Analysis of Nested Search Problems with Applications in Cryptanalysis

André Schrottenloher, Univ Rennes, Inria, IRISA
Marc Stevens, Centrum Wiskunde & Informatica

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 introduces an overhead factor of $(\pi/2)^\ell$ in the complexity (for $\ell$ layers). 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)^\ell$ to $\sqrt{\ell}$; 3) it is simpler to apply and optimize, without needing manual quantum analysis. We give a generic complexity formula that improves the state-of-the-art both for concrete instantiations and in the asymptotic setting. For concrete instances, we show that numerical optimizations enable further improvements over this formula, which results in a further decrease in the gap to an exact quadratic speedup. We demonstrate our framework with applications in cryptanalysis and improve the complexity of quantum attacks on reduced-round AES.

Available format(s)
Attacks and cryptanalysis
Publication info
Quantum searchNested searchQuantum cryptanalysisAmplitude amplificationSymmetric cryptanalysis
Contact author(s)
andre schrottenloher @ inria fr
marc stevens @ cwi nl
2023-05-25: revised
2022-06-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {André Schrottenloher and Marc Stevens},
      title = {A Quantum Analysis of Nested Search Problems with Applications in Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2022/761},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.