Improved Quantum Circuits for AES: Reducing the Depth and the Number of Qubits

Qun Liu, Bart Preneel, Zheng Zhao, Meiqin WangLecture Notes in Computer Science 2023 · DOI · OpenAlexGitHub resource

Abstract

This research presents a suite of optimization techniques designed to minimize the resource requirements for implementing the Advanced Encryption Standard (AES) on quantum computers. By introducing a "mixing-XOR" (m-XOR) technique and a shared pipeline architecture, the authors significantly reduce the number of logical qubits (width) and sequential time steps (depth) required for the AES quantum oracle. These optimizations provide more accurate benchmarks for NIST’s post-quantum security categories, demonstrating that the cost of running Grover’s algorithm against AES is lower than previously estimated.

Introduction

As the cryptographic community prepares for the post-quantum era, the National Institute of Standards and Technology (NIST) has established security levels based on the computational effort required to break current standards like AES. These levels are determined by the cost of Grover’s algorithm, a quantum search that provides a quadratic speedup for key recovery. The primary metrics for this cost are circuit width (qubit count) and depth (time steps). Previous resource estimates were considered potentially conservative; this paper aims to refine these bounds by discovering more efficient quantum circuit implementations for the AES family (AES-128, -192, and -256).

Methodology

The authors propose three primary technical innovations to optimize the quantum oracle, specifically targeting the components of the AES round function.

The standard AES round function components, including SubBytes and MixColumns, which are the primary targets for quantum optimization in this study.
  1. Mixing-XOR (m-XOR) Technique: Quantum circuits often require "ancilla" (scratchpad) qubits for intermediate operations. The m-XOR algorithm identifies when a qubit becomes idle after a linear transformation and repurposes it immediately. This converts "out-of-place" operations into "in-place" ones, effectively reducing the total qubit footprint.
  2. Combined Pipeline & Share Technique: AES utilizes S-boxes for non-linear substitution. To reuse qubits in a pipeline, intermediate values must be "uncomputed" using an inverse S-box. The authors introduce a "water pool" model where the S-box and its inverse share a common pool of ancilla qubits, drawing from and returning to it dynamically rather than treating them as separate, dedicated resources.
  3. MixColumns Optimization: Using a general search algorithm, the authors developed a new implementation for the MixColumns step that is both in-place and achieves a record-low depth of 16.

Key Results and Insights

The proposed methods yield substantial improvements across all AES variants. A critical insight is that ancilla qubits are a recyclable resource; treating them as a shared "water pool" allows for a 59% reduction in the space required for combined S-box and inverse structures. Furthermore, the m-XOR technique demonstrates that reducing width does not necessarily require a sacrifice in T-depth.

A comparison of the Width vs. T-depth trade-off, showing that the circuits proposed in this paper achieve lower width for comparable depths than previous state-of-the-art implementations.

Specific quantitative achievements include:

  • S-box Efficiency: Ancilla qubits for the S-box were reduced from 120 to 83 while maintaining a T-depth of 4.
  • Depth Reductions: Achieved overall circuit depths of 730, 876, and 1,018 for AES-128, -192, and -256, respectively.
  • DW-Cost Improvement: On the zig-zag architecture optimized for low width, the overall Depth-Width (DW) cost for AES-128 was reduced by 35%.

Conclusion

This work establishes new benchmarks for the quantum resource requirements of AES. The techniques introduced—m-XOR and the shared ancilla pool—are generic and can likely be applied to future, more advanced S-box designs to achieve further efficiency gains. These results suggest that NIST's security classifications may need to be adjusted as quantum circuit synthesis continues to improve, narrowing the gap between theoretical security and practical quantum cryptanalysis.

Summary updated

BibTeX
@inproceedings{liu2023improved,
  author = {Qun Liu and Bart Preneel and Zheng Zhao and Meiqin Wang},
  title = {{Improved Quantum Circuits for AES: Reducing the Depth and the Number of Qubits}},
  booktitle = {Lecture Notes in Computer Science},
  year = {2023},
  doi = {10.1007/978-981-99-8727-6\_3},
}
Figure