Skip to Main content Skip to Navigation
Journal articles

Quantum Security Analysis of AES

Abstract : In this paper we analyze for the first time the post-quantum security of AES. AES is the most popular and widely used block cipher, established as the encryption standard by the NIST in 2001. We consider the secret key setting and, in particular, AES-256, the recommended primitive and one of the few existing ones that aims at providing a post-quantum security of 128 bits. In order to determine the new security margin, i.e., the lowest number of non-attacked rounds in time less than 2^128 encryptions, we first provide generalized and quantized versions of the best known cryptanalysis on reduced-round AES, as well as a discussion on attacks that don't seem to benefit from a significant quantum speed-up. We propose a new framework for structured search that encompasses both the classical and quantum attacks we present, and allows to efficiently compute their complexity. We believe this framework will be useful for future analysis. Our best attack is a quantum Demirci-Selçuk meet-in-the-middle attack. Unexpectedly , using the ideas underlying its design principle also enables us to obtain new, counter-intuitive classical TMD trade-offs. In particular, we can reduce the memory in some attacks against AES-256 and AES-128. One of the building blocks of our attacks is solving efficiently the AES S-Box differential equation, with respect to the quantum cost of a reversible S-Box. We believe that this generic quantum tool will be useful for future quantum differential attacks. Judging by the results obtained so far, AES seems a resistant primitive in the post-quantum world as well as in the classical one, with a bigger security margin with respect to quantum generic attacks.
Document type :
Journal articles
Complete list of metadatas

Cited literature [44 references]  Display  Hide  Download

https://hal.inria.fr/hal-02397049
Contributor : André Schrottenloher <>
Submitted on : Friday, December 6, 2019 - 1:00:44 PM
Last modification on : Tuesday, December 31, 2019 - 4:48:17 PM
Long-term archiving on: : Saturday, March 7, 2020 - 2:46:25 PM

File

8314-Article Text-4518-1-10-20...
Files produced by the author(s)

Identifiers

Collections

Citation

Xavier Bonnetain, María Naya-Plasencia, André Schrottenloher. Quantum Security Analysis of AES. IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2019, 2019 (2), pp.55-93. ⟨10.13154/tosc.v2019.i2.55-93⟩. ⟨hal-02397049⟩

Share

Metrics

Record views

178

Files downloads

328