Quantum Analysis of AES

Our work explores the key recovery attack using the Grover's search on the three variants of AES (-128, -192, -256). In total, we develop a pool of 26 implementations per AES variant (totaling 78), by taking the state-of-the-art advancements in the relevant fields into account. 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 report corrected benchmarks (which seem to improve from the authors' own bug-fixing, thanks to our architecture consideration). 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. To be more precise, we estimate the currently best-known quantum attack complexities for AES-128 (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>156.2630</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math>), AES-192 (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>221.5801</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math>) and AES-256 (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>286.0731</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:math>). Additionally, we achieve the least Toffoli depth - qubit count product for AES-128 (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>121920</mml:mn> </mml:mrow> </mml:math>, improving from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>130720</mml:mn> </mml:mrow> </mml:math> by Shi and Feng in Asiacrypt'24), AES-192 (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>161664</mml:mn> </mml:mrow> </mml:math>, improving from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>188880</mml:mn> </mml:mrow> </mml:math> by Liu et al. in Asiacrypt'23) and AES-256 (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>206528</mml:mn> </mml:mrow> </mml:math>, improving from <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>248024</mml:mn> </mml:mrow> </mml:math> by Liu et al. in Asiacrypt'23) so far. 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, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> </mml:math>-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 like depth-squared - qubit count product, depth - gate count product.