Skip to Main content Skip to Navigation
Conference papers

Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm

Abstract : In symmetric cryptanalysis, the model of superposition queries has led 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 with Grover's algorithm. In particular, we are able to break the Even-Mansour construction in quantum time $Õ(2^{n/}3)$, with $O(2^{n/3})$ classical queries and $O(n^2)$ qubits only. In addition, we 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 superpo-sition 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.
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download

https://hal.inria.fr/hal-02397056
Contributor : André Schrottenloher <>
Submitted on : Friday, December 6, 2019 - 1:07:37 PM
Last modification on : Tuesday, December 31, 2019 - 5:03:30 PM
Long-term archiving on: : Saturday, March 7, 2020 - 2:42:31 PM

File

simoncombi-eprint.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, André Schrottenloher. Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm. ASIACRYPT 2019 - 25th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2019, Kobe, Japan. pp.552-583, ⟨10.1007/978-3-030-34578-5_20⟩. ⟨hal-02397056⟩

Share

Metrics

Record views

100

Files downloads

329