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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Quantum searchNested searchQuantum cryptanalysisAmplitude amplificationSymmetric cryptanalysis
Contact author(s)
andre schrottenloher @ inria fr
marc stevens @ cwi nl
History
2023-05-25: revised
2022-06-14: received
See all versions
Short URL
https://ia.cr/2022/761
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/761,
      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{https://eprint.iacr.org/2022/761}},
      url = {https://eprint.iacr.org/2022/761}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.