Quantum Security Analysis of AES
Open accessThe DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
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 2128 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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680
On the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Biclique Cryptanalysis of the Full AES
Bogdanov, A., Khovratovich, D., & Rechberger, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_19 · Cited by 546
Improved Cryptanalysis of Rijndael
Ferguson, N., Kelsey, J., Lucks, S., Schneier, B., Stay, M., Wagner, D., & Whiting, D. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44706-7_15 · Cited by 449
Applying Grover’s Algorithm to AES: Quantum Resource Estimates
Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-29360-8_3 · Cited by 299
Quantum cryptanalysis of hash and claw-free functions: Invited paper
Brassard, G., HØyer, P., & Tapp, A. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0054319 · Cited by 251
A Meet-in-the-Middle Attack on 8-Round AES
Demirci, H., & Selçuk, A. A. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-71039-4_7 · Cited by 207
Cited by
Implementing Grover Oracles for Quantum Key Search on AES and LowMC
Jaques, S., Naehrig, M., Roetteler, M., & Virdia, F. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45724-2_10 · Cited by 234
Szymanski, T. H. (2022) · IEEE Access · doi:10.1109/access.2022.3169137 · Cited by 59
Quantum Safe Lightweight Cryptography with Quantum Permutation Pad
Kuang, R., Lou, D., He, A., & Conlon, A. (2021) · 2021 IEEE 6th International Conference on Computer and Communication Systems (ICCCS) · doi:10.1109/icccs52626.2021.9449247 · Cited by 21
Metadata
- Authors
- Bonnetain, X., Naya-Plasencia, M., & Schrottenloher, A.
- Venue
- IACR Transactions on Symmetric Cryptology
- Published
- 2019-06-11
- Pages
- 55-93
- ISSN
- 2519-173X (ISSN-L)
- OpenAlex
- W4250498021
- Cited by
- 173
- References
- 9
- FWCI
- 7.71
- Type
- journal article
- Language
- en
- Open access
- diamond
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.