Welcome to the resource topic for 2022/761
Title:
A Quantum Analysis of Nested Search Problems with Applications in Cryptanalysis
Authors: André Schrottenloher and Marc Stevens
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.
ePrint: https://eprint.iacr.org/2022/761
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .