Paper 2022/761
Quantum Procedures for 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 of
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in CIC 2024
- DOI
- 10.62056/aee0fhbmo
- Keywords
- Quantum searchNested searchQuantum cryptanalysisAmplitude amplificationSymmetric cryptanalysis
- Contact author(s)
-
andre schrottenloher @ inria fr
marc stevens @ cwi nl - History
- 2024-11-08: last of 3 revisions
- 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 = {Quantum Procedures for Nested Search Problems with Applications in Cryptanalysis}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/761}, year = {2022}, doi = {10.62056/aee0fhbmo}, url = {https://eprint.iacr.org/2022/761} }