Substitution boxes (S-boxes) serve as fundamental non-linear components in symmetric cryptography, and their quantum circuit implementation is critical for quantum security. This work addresses the dual challenges of quantum circuit depth optimization and computational intractability in S-box synthesis. We introduce memory-optimized data structures, a pointer-efficient RandomAccessSet and a dynamic devector, that reduce memory overhead by 12 times per element, thereby mitigating the computational complexity associated with Pauli representation. Our enhanced Meet-in-the-Middle framework achieves exhaustive depth optimization for standardized S-boxes, demonstrating up to 8.5% depth reduction over DORCIS baselines at equivalent T-depth. The approach scales to 5-8-bit primitives, establishing memory efficiency as an independent resource dimension in quantum circuit synthesis. Comparative analysis under varied cost parameters provides new insights for resource-efficient cryptographic implementations on quantum hardware.
Substitution boxes (S-boxes) serve as fundamental non-linear components in symmetric cryptography, and their quantum circuit implementation is critical for quantum security. This work addresses the dual challenges of quantum circuit depth optimization and computational intractability in S-box synthesis. We introduce memory-optimized data structures, a pointer-efficient RandomAccessSet and a dynamic devector, that reduce memory overhead by 12 times per element, thereby mitigating the computational complexity associated with Pauli representation. Our enhanced Meet-in-the-Middle framework achieves exhaustive depth optimization for standardized S-boxes, demonstrating up to 8.5% depth reduction over DORCIS baselines at equivalent T-depth. The approach scales to 5-8-bit primitives, establishing memory efficiency as an independent resource dimension in quantum circuit synthesis. Comparative analysis under varied cost parameters provides new insights for resource-efficient cryptographic implementations on quantum hardware.
In this paper, we consider the problem of quantum implementation of the symmetric-key ciphers. The typical ciphers in this category have two main components, the linear and the non-linear layers, we consider both. The linear layer can be described as a non-singular matrix over binary operations. The in-place implementation is one of the main considerations for implementing such layer to minimize the number of qubits. We discuss the research works that have been done to this point on this subject matter and report the improved implementation of some of the matrices. Lists of our modifications include; making it more efficient (specially for the larger matrices), consideration for quantum depth (along with a randomized algorithm for optimization), etc. We report benchmarks for the ASCON and SHA-2 linear matrices. As for the non-linear layer, the constituent block is called an substitution box (an S-box, for short). Our “DORCIS” tool presented in this paper, finds a quantum circuit with an optimized depth for given S-boxes of size 3- and 4-bit. It is a follow-up work on LIGHTER-R (which is applicable for 4-bit S-boxes only) with multiple extensions. Unlike LIGHTER-R, our DORCIS takes a quantum decomposition based on Clifford and T gates. Also, both the full quantum depth and the T depth can be optimized by DORCIS. We compare our implementation with other optimized quantum circuits shown in the other research works and show that we find an implementation with the same cost metric, or find an implementation with lower cost metric, compared other tools proposed in the literature, apart from being simpler and more efficient.
Modern information security relies heavily on symmetric-key cryptography such as AES. As quantum computing advances, these classical schemes face increasing pressure from quantum key-search attacks, most notably Grover’s algorithm. To evaluate and compare quantum security quantitatively, the core components of symmetric-key algorithms must be implemented and optimized as quantum circuits. Among them, the S-box is a key source of nonlinearity and often dominates the circuit cost. In this paper, we introduce ADOQ (Automatic Depth Optimizer for Quantum circuits), a modular Python (version 3.13.3) framework that automatically synthesizes reversible quantum circuits from S-box specifications and applies a sequence of depth optimization techniques to produce optimized QASM circuits. Our experiments show that ADOQ achieves circuit depths comparable to prior work on 4-qubit S-boxes, and it also supports synthesis for larger S-boxes.
With the development of quantum computing technology, efficiently implementing the core component S-box of block ciphers in quantum environments has become an important research direction in the field of cryptographic engineering. Due to the limitations of the no-cloning theorem of quantum states, the implementation of S-boxes in quantum circuits faces the dual challenges of exponential growth in space complexity and excessive consumption of quantum resources, especially in 16-bit and larger S-boxes. To address these problems, this paper proposes a construction framework for 16-bit S-box quantum circuits based on composite fields. This method relies on normal bases representation to construct composite field structures, decomposing high-dimensional multiplicative inverse into low-dimensional subdomain operations through isomorphic mapping, thereby significantly reducing the quantum cost of nonlinear component. In the linear component, a dynamic optimal pivot selection strategy is proposed to effectively optimize the Gaussian elimination process while maintaining the row echelon form of the matrix, thereby reducing the number of CNOT gates. Taking the 16-bit S-box in the MK-3 algorithm as an example, experimental results show that the proposed method maintains correct circuit structure while reducing CNOT gate consumption in the linear component by more than 32.8%, and the utilization of quantum resources in the nonlinear component is more advantageous. This study provides theoretical support and an implementation path for the high-performance implementation of block ciphers in practical quantum computing environments.
With the continuous development of quantum technology and the gradual advancement of quantum computers, the challenges faced by modern cryptography are becoming increasingly diverse. When analyzing the security strength of cryptographic algorithms against quantum attacks, the construction of quantum implementation circuits is a crucial aspect. Symmetric-key cryptography is an important component of modern cryptography. This study reviews the research results of optimizing the quantum implementation of symmetric-key cryptography under quantum computing models. Specifically, this work summarizes the construction of reversible circuits for linear layers, Substitution-boxes (S-boxes), and various addition operations, as well as the quantum implementation of symmetric-key ciphers such as AES, SM4, and Camellia.
An efficient quantum implementation of the advanced encryption standard (AES) is crucial for reducing the complexity of implementing an exhaustive key search through Grover’s algorithm. In this paper, we study how to construct resource-efficient quantum circuits for AES. We consider the product of T-gates depth and width (TDW) and the product of full depth and width (FDW) as optimization targets. We propose a generic method, called the controlled control qubit cascade (CCQC) technique, to construct quantum circuits for nonlinear components with reduced TDW and FDW. Using this, we construct a quantum circuit for the AES S-box. Compared with recent work presented at ASIACRYPT 2023, our S-box quantum circuit achieves reductions of 2.3% in TDW and 45.2% in FDW. Additionally, we propose a new key schedule strategy to reduce the full depth of the AES quantum circuit. Finally, the trade-offs between T-gates depth and width and the parallel numbers of S-box and TDW are analyzed.
Abstract With the rapid development of quantum technology, modern cryptography is facing an increasing number of security threats. Given that the quantum circuit of symmetric‐key ciphers frequently serves as the core element of quantum attacks, it has attracted extensive attention. In this work, it is investigated that how the quantum circuit of SM4 and Camellia can be implemented with lower ‐depth. First, a general framework is proposed for designing Substitution‐box (S‐box) circuits with optimized ‐depth. Based on the framework, quantum circuits are respectively designed for SM4 S‐box and Camellia S‐box with ‐depth 4. Compared with existing quantum circuits requiring a ‐depth of 4, our circuits consume fewer qubits and quantum gates, as well as lower full depth. Besides, S‐box quantum circuits are introduced with ‐depth 3 for SM4 and Camellia for the first time. As an application, the designed S‐box circuits can reduce the ‐depth requiring for the subroutine and stand‐alone circuits of SM4 from 132 and 260 in the previous work to 99 and 195. Additionally, the ‐depth requiring for the subroutine and stand‐alone circuits of Camellia‐128/‐192/‐256 can be reduced from 92/126/126 and 108/150/150 in the previous work to 70/96/96 and 82/114/114, respectively.