Optimizing the quantum circuit for implementing Advanced Encryption Standard (AES) is crucial for estimating the necessary resources in attacking AES by the 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. AimTaking aim at this task, we find a method for how the quantum circuit of AES S-box can be designed with the help of the automation tool LIGHTER-R. Particularly, the multiplicative inversion in F28 , which is the main part of the S-box, is converted into the multiplicative inversion (and multiplication) in F24 , 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. In addition, 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.
In the post-quantum era, the security level of encryption algorithms is often evaluated based on the quantum resources required to attack AES. In this work, we make thoroughly estimations on various performance metrics of the quantum circuit of AES-128/192/256. Firstly, we introduce a generic round structure for in-place implementation of the AES algorithm, maximizing the parallelism between nonlinear components. Specifically, when employed as an encryption oracle, our structure reduces the
T-depth from
2rdto
(r+1)d. Furthermore, by leveraging the properties of block-cyclic matrices, we present an in-place implementation circuit for MixColumn with depth 10, utilizing 105 CNOT gates. In relation to the S-box, we have assessed its minimum circuit width at different
T-depths and provide multiple versions of circuit implementations for a depth-width trade-off. Finally, based on our optimized S-box circuit, we conduct a comprehensive analysis of the implementation complexity of different round structures, where our structure exhibits significant advantages in terms of low
T-depth.
Grover’s search algorithm allows a quantum adversary to find a
k-bit secret key of a block cipher by making O(
2k/2) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the
T-depth of its circuit implementation and the number of qubits used by the circuit (width). Since the AES S-box is the only component which requires
T-gates in a quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low
T-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose three methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular, one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its
T-depth.