New record in the number of qubits for a quantum implementation of AES

Zhenqiang Li; Fei Gao; Sujuan Qin; Qiaoyan Wen

Paper 2023/018

New record in the number of qubits for a quantum implementation of AES

Zhenqiang Li, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China, Henan Key Laboratory of Network Cryptography Technology, Zhengzhou, China

Fei Gao, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China

Sujuan Qin, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China

Qiaoyan Wen, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China

Abstract

Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by Grover algorithm. Previous studies have reduced the number of qubits required for the quantum circuits of AES-128/-192/-256 from 984/1112/1336 to 270/334/398, which is close to the optimal value of 256/320/384. It becomes a challenging task to further optimize them. Aiming at this task, we find a method about how the quantum circuit of AES S-box can be designed with the help of automation tool LIGHTER-R. Particularly, the multiplicative inversion in F_2^8, which is the main part of S-box, is converted into the multiplicative inversion (and multiplication) in F_2^4, then the latter can be implemented by LIGHTER-R because its search space is small enough. By this method, we construct the quantum circuits of S-box for mapping |a>|0> to |a>|S(a)> and |a>|b> to |a>|b+S(a)> with 20 qubits instead of 22 in the previous studies. Besides, we introduce new techniques to reduce the number of qubits required by the S-box circuit for mapping |a> to |S(a)>from 22 in the previous studies to 16. Accordingly, we synthesize the quantum circuits of AES-128/-192/-256 with 264/328/392 qubits, which implies a new record.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: AES S-box quantum circuit multiplication inversion
Contact author(s): gaof @ bupt edu cn
qsujuan @ bupt edu cn
wqy @ bupt edu cn
History: 2023-01-05: approved; 2023-01-05: received; See all versions
Short URL: https://ia.cr/2023/018
License: CC BY

BibTeX

@misc{cryptoeprint:2023/018,
      author = {Zhenqiang Li and Fei Gao and Sujuan Qin and Qiaoyan Wen},
      title = {New record in the number of qubits for a quantum implementation of AES},
      howpublished = {Cryptology ePrint Archive, Paper 2023/018},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/018}},
      url = {https://eprint.iacr.org/2023/018}
}