Paper 2022/683
Quantum Analysis of AES
Abstract
Quantum computing is considered one of the next big leaps in computational science. While a fully functional quantum computer is still in the future, there is an ever-growing need to evaluate the security of the symmetric key ciphers against a potent quantum adversary. Keeping this in mind, our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). We develop a pool of 26 implementations per AES variant (thus totaling 78), by taking the state-of-the-art advancements in the relevant fields into account.
In a nutshell, we present the least Toffoli depth and full depth implementations of AES, thereby improving from Zou et al.'s Asiacrypt'20 paper by more than 97 percent for each variant of AES. We show that the qubit count - Toffoli depth product is reduced from theirs by more than 87 percent. Furthermore, we analyze the Jaques et al.'s Eurocrypt'20 implementations in detail, fix the bugs (arising from some problem of the quantum computing tool used and not related to their coding), and report corrected benchmarks. To the best of our finding, our work improves from all the previous works (including the Asiacrypt'22 paper by Huang and Sun, the Asiacrypt'23 paper by Liu et al. and the Asiacrypt'24 paper by Shi and Feng) in terms of various quantum circuit complexity metrics (Toffoli depth, full depth, Toffoli/full depth - qubit count product, full depth - gate count product, etc.). Also, our bug-fixing of Jaques et al.'s Eurocrypt'20 implementations seems to improve from the authors' own bug-fixing, thanks to our architecture consideration.
Equipped with the basic AES implementations, we further investigate the prospect of the Grover's search. We propose four new implementations of the S-box, one new implementation of the MixColumn; as well as five new architecture (one is motivated by the architecture by Jaques et al. in Eurocrypt'20, and the rest four are entirely our innovation). Under the MAXDEPTH constraint (specified by NIST), the circuit depth metrics (Toffoli depth, T-depth and full depth) become crucial factors and parallelization for often becomes necessary. We provide the least depth implementation in this respect that offers the best performance in terms of metrics for circuit complexity (like, depth-squared - qubit count product, depth - gate count product).
Thus, to our knowledge, we estimate the currently best-known quantum attack complexities for AES-128 (
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- A minor revision of an IACR publication in CIC 2025
- DOI
- 10.62056/ay11zo-3y
- Keywords
- Quantum ImplementationGrover's SearchAES
- Contact author(s)
-
starj1023 @ gmail com
anubhab001 @ e ntu edu sg
khj1594012 @ gmail com
thdrudwn98 @ gmail com
hwajeong84 @ gmail com
anupam @ ntu edu sg - History
- 2025-04-05: last of 38 revisions
- 2022-05-31: received
- See all versions
- Short URL
- https://ia.cr/2022/683
- License
-
CC BY-NC-SA
BibTeX
@misc{cryptoeprint:2022/683, author = {Kyungbae Jang and Anubhab Baksi and Hyunji Kim and Gyeongju Song and Hwajeong Seo and Anupam Chattopadhyay}, title = {Quantum Analysis of {AES}}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/683}, year = {2022}, doi = {10.62056/ay11zo-3y}, url = {https://eprint.iacr.org/2022/683} }