Cryptology ePrint Archive: Report 2020/941

Towards Optimizing Quantum Implementation of AES S-box

Doyoung Chung and Jooyoung Lee and Seungkwang Lee and Dooho choi

Abstract: 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 (time) and the number of qubits used by the circuit (space). Since the AES S-box is the only component which requires T-gates in the 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 seven 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.

Category / Keywords: secret-key cryptography / Quantum implementation, quantum cryptanalysis, Grover's algorithm, AES, multiplicative inversion

Date: received 31 Jul 2020, last revised 8 Sep 2020

Contact author: thisisdoyoung at etri re kr

Available format(s): PDF | BibTeX Citation

Version: 20200908:071608 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]