Paper 2019/614
Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm
Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, and André Schrottenloher
Abstract
In symmetric cryptanalysis, the model of superposition queries has lead to surprising results, with many constructions being broken in polynomial time thanks to Simon's period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive.
In this paper, we introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search using Grover's algorithm. In particular, we are able to break the Even-Mansour construction in quantum time
Note: Updated to IACR version
Metadata
- Available format(s)
- Category
- Secret-key cryptography
- Publication info
- Published by the IACR in ASIACRYPT 2019
- Keywords
- Simon's algorithmclassical queriessymmetric cryptographyquantum cryptanalysisEven-Mansour constructionFX construction
- Contact author(s)
- xavier bonnetain @ inria fr
- History
- 2019-09-09: last of 2 revisions
- 2019-06-03: received
- See all versions
- Short URL
- https://ia.cr/2019/614
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/614, author = {Xavier Bonnetain and Akinori Hosoyamada and María Naya-Plasencia and Yu Sasaki and André Schrottenloher}, title = {Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/614}, year = {2019}, url = {https://eprint.iacr.org/2019/614} }