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 $O(2^{n/3})$, with $O(2^{n/3})$ classical queries and $O(n^2)$ qubits only. In addition, we propose an algorithm that allows to improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity. Our approach can be seen in two complementary ways: reusing superposition queries during the iteration of a search using Grover's algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure. We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

Note: Updated to IACR version

Metadata
Available format(s)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2019/614}},
      url = {https://eprint.iacr.org/2019/614}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.