Paper 2022/761
A Quantum Analysis of Nested Search Problems with Applications in Cryptanalysis
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)
- 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
-
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} }