Serpent, one of the AES candidate algorithms, is known for its high security and attack resistance. It is suitable for areas with high information security requirements. Serpent's distinctive nonlinear structure is the S-boxes. This paper studies how to build the quantum circuit for Serpent algorithm with lower costs. By combining with the quantum circuits of S-boxes with fewer qubits and quantum gates and the inverse quantum circuits of S-boxes, the key expansion quantum circuit can be constructed. Moreover, by decomposing the 3-controlledCNOT gates appearing in the quantum circuits of the S-boxes and optimizing the decomposed quantum circuits, the number of Toffoligates is further reduced. In conjunction with the proposed quantum circuits, two types of quantum circuits requiring 448 qubits and 92288 T gates and 384 qubits and 118944 T gates are given to realize the Serpent algorithm. In comparison with the previous study, which required 800 qubits and 132608 T gates, the quantum circuit in this paper requires fewer resources. Furthermore, the S-boxes and key expansion quantum circuits used in the study can reduce the quantum resources in implementing Serpent, reducing the quantum circuit scale required to attack Serpent by the Grover algorithm.
Serpent, one of the AES candidate algorithms, is known for its high security and attack resistance. It is suitable for areas with high information security requirements. Serpent's distinctive nonlinear structure is the S-boxes. This paper studies how to build the quantum circuit for Serpent algorithm with lower costs. By combining with the quantum circuits of S-boxes with fewer qubits and quantum gates and the inverse quantum circuits of S-boxes, the key expansion quantum circuit can be constructed. Moreover, by decomposing the 3-controlledCNOT gates appearing in the quantum circuits of the S-boxes and optimizing the decomposed quantum circuits, the number of Toffoligates is further reduced. In conjunction with the proposed quantum circuits, two types of quantum circuits requiring 448 qubits and 92288 T gates and 384 qubits and 118944 T gates are given to realize the Serpent algorithm. In comparison with the previous study, which required 800 qubits and 132608 T gates, the quantum circuit in this paper requires fewer resources. Furthermore, the S-boxes and key expansion quantum circuits used in the study can reduce the quantum resources in implementing Serpent, reducing the quantum circuit scale required to attack Serpent by the Grover algorithm.
Camellia, after AES, is one of the most competitive block cipher algorithms. It has been widely used in many fields of information security. Camellia's distinctive nonlinear component is the S-box. This paper studies how to build the quantum circuit of the Camellia S-box at lower costs. First, the multiplicative inversion in F_2^8can be obtained by the multiplicative inversion (and multiplication) in F_2^4via a mapping matrix, and the latter can be implemented by the automation tool LIGHTER-R. The affine transformation of the S-box is then implemented with CNOT and NOT gates using the PLU decomposition and elimination approach. Finally, the Camellia S-box quantum circuit is built with 20 qubits, 54 Toffoli gates, 196 CNOT gates, 13 NOT gates, and a Toffoli depth of 42. In comparison with the previous study, which required 23 qubits, 67 Toffoli, and 38 CNOT gates, and a Toffoli depth of 53, the S-box quantum circuit in this paper requires fewer resources. Furthermore, the S-box quantum circuit used in the study can reduce the quantum resources in implementing Camellia, reducing the quantum circuit scale required to attack Camellia by the Grover algorithm.
Abstract Quantum computing poses a significant threat to modern cryptosystems, prompting nations to initiate the development of next-generation cryptographic algorithms where quantum security assessment constitutes a critical task. In this work, we present the first complete quantum attack circuit construction and security evaluation of quantum resistance for the authenticated encryption algorithm MK-3, which features 16-bit S-boxes. Firstly, we achieve breakthroughs in finite field arithmetic. The arrangement method of Toffoli gates in the subfield F24 F 2 4 enables two types of optimized F28 F 2 8 multiplication circuits to reduce DW-cost by at least 50%. For F28 F 2 8 inversion, by proposing a new intermediate state uncomputing technique, the DW-cost of the inversion circuit is reduced by at least 40% compared with existing solutions. This can also be used to optimize the quantum circuits of block ciphers such as AES and SM4. Secondly, we propose three types of quantum circuits for MK-3’s 16-bit S-box. The basic circuit reduces multiplicative bit operations to 115, representing at least 20% reduction. We propose a more compact S-box structure, reducing the number of circuit qubits for two types of S-boxes from 52 to 40. Finally, we implement full-algorithm quantum attacks and conduct security evaluations for MK-3. Complete quantum circuits supporting 128-bit and 256-bit keys are constructed, enabling Grover key search attacks. Security assessments confirm the 128-bit version meets NIST Security Category 1 (with reasonable inference of achieving Category 2), while the 256-bit version satisfies the highest Category 5 standards, demonstrating resistance against large-scale quantum computing attacks. This work achieves the first quantum circuit implementation for 16-bit S-boxes and provides critical evaluation benchmarks for post-quantum cryptography standardization.
With the advancement of quantum computing, quantum circuit implementations of symmetric cryptographic algorithms are essential for evaluating their resistance to quantum attacks. As an ISO-standardized cipher, the efficient quantum circuit construction of Camellia is of great significance. Focusing on minimizing the DW-cost (qubits × Toffoli-depth) while balancing ancilla qubits and Toffoli-depth, this paper proposes an optimized quantum circuit design for Camellia. Specifically: (1) using a serial-multiplication and out-of-place inversion architecture under composite-field decomposition, combined with hierarchical screening for parallelizing bilinear multiplications, a compact in-place S-box quantum circuit is constructed with a DW-cost of 276, 28% lower than the state of the art; (2) a low-gate-count linear-layer circuit is obtained via heuristic search, and gate-sequence reordering then reduces the full depth from 9 to 7 without increasing the gate count; (3) Camellia-128/192/256 quantum circuits are constructed with DW-costs of 119,168, 257,664, and 257,664, achieving reductions of 48%, 52%, and 52% respectively over prior work. A pipelined Grover oracle is further designed and the total resources required for a full Grover search attacking Camellia are evaluated. For Camellia-128, the complete Grover search requires a T-depth of 2.10 × 2⁷⁶ and a total TDW-cost (qubits × T-depth) of 1.00 × 2⁸⁶, reducing T-depth by 75% and TDW-cost by 84% over prior work. The first full Grover search resource estimates for Camellia-192/256 are also presented, with T-depths of 7.20 × 2¹⁰⁸ and 8.11 × 2¹⁴⁰ and TDW-costs of 2.03 × 2¹²³ and 2.79 × 2¹⁵³, respectively. These results show that Grover's attack on Camellia requires fewer quantum resources than on AES at the 128-bit level, implying comparatively weaker post-quantum security at that key size, while the picture reverses at larger key sizes (Section 4).
To quantify security levels in a postquantum scenario, it is common to use the quantum resources needed to attack the Advanced Encryption Standard (AES) as a reference value. Specifically, in the National Institute of Standards and Technology's ongoing postquantum standardization effort, different security categories are defined that reflect the quantum resources needed to attack AES-128, AES-192, and AES-256. This article presents a quantum circuit to implement the S-box of AES. Also, leveraging 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.
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.
To quantify security levels in a postquantum scenario, it is common to use the quantum resources needed to attack the Advanced Encryption Standard (AES) as a reference value. Specifically, in the National Institute of Standards and Technology's ongoing postquantum standardization effort, different security categories are defined that reflect the quantum resources needed to attack AES-128, AES-192, and AES-256. This article presents a quantum circuit to implement the S-box of AES. Also, leveraging 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.