Paper 2019/854

Reducing the Cost of Implementing AES as a Quantum Circuit

Brandon Langenberg and Hai Pham and Rainer Steinwandt

Abstract

To quantify security levels in a post-quantum scenario, it is common to use the quantum resources needed to attack AES as a reference value. Specifically, in NIST’s ongoing post-quantum standardization effort, different security categories are defined that reflect the quantum resources needed to attack AES-128, AES-192, and AES-256. This paper presents a quantum circuit to implement the S-box of AES. Leveraging also an improved implementation of the key expansion, we identify new quantum circuits for all three AES key lengths. For AES-128, the number of Toffoli gates can be reduced by more than 88% compared to Almazrooie et al.'s and Grassl et al.'s estimates, while simultaneously reducing the number of qubits. Our circuits can be used to simplify a Grover-based key search for AES.