Paper 2022/761

A Quantum Analysis of Nested Search Problems with Applications in Cryptanalysis

André Schrottenloher, Centrum Wiskunde & Informatica
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 as well as constraints. Classical nested searches can be transformed into quantum algorithms, using Grover's quantum search or amplitude amplification by Brassard et al., obtaining up to a square-root speedup. However, the nesting introduces technicalities in the quantum complexity analysis that are complex to handle and have been so far analyzed in previous works in a case-by-case manner. In this paper, we aim to simplify the quantum transformation and corresponding analysis. We introduce a framework to transform classical nested searches into a quantum procedure and to analyze its complexity. The resulting quantum procedure is easier to describe and analyze compared to previous works, both in the asymptotic setting and for concrete instantiations. Its time complexity and success probability can be bounded using a generic formula, or more precisely with numerical optimization. Along the way to this result, we introduce an algorithm for variable-time amplitude amplification of independent interest. It allows to obtain essentially the same asymptotic complexity as a previous algorithm by Ambainis (STACS 2012) using only several layers of amplitude amplification, and without relying on amplitude estimation. Moreover, we present some direct applications of our results in cryptanalysis.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Quantum search Nested search Quantum cryptanalysis Amplitude amplification Symmetric cryptanalysis
Contact author(s)
andre schrottenloher @ cwi nl
marc stevens @ cwi nl
History
2022-06-16: approved
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.