Paper 2025/1494 Original: eprint.iacr.org/2025/1494 ↗

Quantum Circuit Synthesis for AES with Low DW-cost

Abstract

Symmetric cryptography is confronting threats posed by quantum computing, including Grover's search algorithm and Simon's algorithm. In the fault-tolerant quantum computation, the limited qubit count, connectivity constraints, and error rates of quantum hardware impose stringent requirements on the implementation of cryptographic quantum circuits. Constructing low-resource quantum circuit models forms the foundation for evaluating algorithmic resistance to quantum threats. At CRYPTO 2019, Jaques et al. justified the adoption of depth-times-width cost (DW-cost) as a metric for quantum circuits by incorporating advancements in quantum computation and error correction. In this work, we address the fundamental limitations in in-place implementations of AES quantum circuits by proposing a set of in-place synthesis methods centered on DW-cost optimization. First, we prove that within the composite field arithmetic framework, intermediate circuit states can be utilized to uncompute S-box input states, and introduce a novel design pathway and circuit structure for in-place S-box quantum circuits. Second, we establish the necessary conditions for maximizing parallelization of Toffoli gates under minimal-width constraints in binary field multiplication. Through co-design and optimization of multiple nonlinear components, we construct a compact in-place S-box with a DW-cost of merely 276. Finally, building on this, we achieve quantum circuit implementations for AES-128, AES-192, and AES-256 via co-optimization of key expansion and round functions, reducing their DW-cost values to 65,280, 87,552, and 112,896 respectively. These results indicate a reduction of at least 46%, 45%, and 45% compared to existing state-of-the-art solutions. This study establishes new technical benchmarks for low-resource fault-tolerant implementations of symmetric cryptography in the post-quantum era. (This is a revised version containing Clifford+T resource estimates for both AES-128 Grover oracle and encryption oracle. Key revisions are highlighted in red.)