Paper 2024/381

Quantum Circuits of AES with a Low-depth Linear Layer and a New Structure

Haotian Shi, Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, University of Chinese Academy of Sciences
Xiutao Feng, Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences
Abstract

In recent years quantum computing has developed rapidly. The security threat posed by quantum computing to cryptography makes it necessary to better evaluate the resource cost of attacking algorithms, some of which require quantum implementations of the attacked cryptographic building blocks. In this paper we manage to optimize quantum circuits of AES in several aspects. Firstly, based on de Brugière \textit{et al.}'s greedy algorithm, we propose an improved depth-oriented algorithm for synthesizing low-depth CNOT circuits with no ancilla qubits. Our algorithm finds a CNOT circuit of AES MixColumns with depth 10, which breaks a recent record of depth 16. In addition, our algorithm gives low-depth CNOT circuits for many MDS matrices and matrices used in block ciphers studied in related work. Secondly, we present a new structure named compressed pipeline structure to synthesize quantum circuits of AES, which can be used for constructing quantum oracles employed in quantum attacks based on Grover and Simon's algorithms. When the number of ancilla qubits required by the round function and its inverse is not very large, our structure will have a better trade-off of $D$-$W$ cost. We then give detailed quantum circuits of AES-128 under the guidance of our structure and make some comparisons with other circuits. Finally, our encryption circuit and key schedule circuit have their own application scenarios. The Encryption oracle used in Simon's algorithm built with the former will have smaller depth. For example, we can construct an AES-128 Encryption oracle with $T$-depth 33, while the previous best result is 60. A small variant of the latter, along with our method to make an Sbox input-invariant, can avoid the allocation of extra ancilla qubits for storing key words in the shallowed pipeline structure. Based on this, we achieve a quantum circuit of AES-128 with the lowest $TofD$-$W$ cost 130720 to date.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Quantum circuitDepthAESEncryption oracle
Contact author(s)
shihaotian @ amss ac cn
fengxt @ amss ac cn
History
2024-03-04: approved
2024-03-01: received
See all versions
Short URL
https://ia.cr/2024/381
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/381,
      author = {Haotian Shi and Xiutao Feng},
      title = {Quantum Circuits of {AES} with a Low-depth Linear Layer and a New Structure},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/381},
      year = {2024},
      url = {https://eprint.iacr.org/2024/381}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.