Security vulnerabilities in the symmetric-key primitives of a cipher can undermine the overall security claims of the cipher. With the rapid advancement of quantum computing in recent years, there is an increasing effort to evaluate the security of symmetric-key cryptography against potential quantum attacks. This paper focuses on analyzing the quantum attack resistance of AIM, a symmetric-key primitive used in the AIMer digital signature scheme. We present the first quantum circuit implementation of AIM and estimate its complexity (such as qubit count, gate count, and circuit depth) with respect to Grover’s search algorithm. For Grover’s key search, the most important optimization metric is depth, especially when considering parallel search. Our implementation gathers multiple methods for a low-depth quantum circuit of AIM in order to reduce the Toffoli depth and full depth (such as the Karatsuba multiplication and optimization of inner modules; Mer, LinearLayer).
Security vulnerabilities in the symmetric-key primitives of a cipher can undermine the overall security claims of the cipher. With the rapid advancement of quantum computing in recent years, there is an increasing effort to evaluate the security of symmetric-key cryptography against potential quantum attacks. This paper focuses on analyzing the quantum attack resistance of AIM, a symmetric-key primitive used in the AIMer digital signature scheme. We present the first quantum circuit implementation of AIM and estimate its complexity (such as qubit count, gate count, and circuit depth) with respect to Grover’s search algorithm. For Grover’s key search, the most important optimization metric is depth, especially when considering parallel search. Our implementation gathers multiple methods for a low-depth quantum circuit of AIM in order to reduce the Toffoli depth and full depth (such as the Karatsuba multiplication and optimization of inner modules; Mer, LinearLayer).
Quantum computing advancements pose security challenges for cryptography. Specifically, Grover’s search algorithm affects the reduction in the search complexity of symmetric-key encryption and hash functions. Recent efforts have been made to estimate the complexity of Grover’s search and evaluate post-quantum security. In this paper, we propose a depth-optimized quantum circuit implementation for ASCON, including both symmetric-key encryption and hashing algorithms, as a part of the lightweight cryptography standardization by NIST (National Institute of Standards and Technology). As far as we know, this is the first implementation of a quantum circuit for the ASCON AEAD (Authenticated Encryption with Associated Data) scheme, which is a symmetric-key algorithm. Also, our quantum circuit implementation of the ASCON-HASH achieves a reduction of more than 88.9% in the Toffoli depth and more than 80.5% in the full depth compared to the previous work. As per our understanding, the most effective strategy against Grover’s search involves minimizing the depth of the quantum circuit for the target cipher. We showcase the optimal Grover’s search cost for ASCON and introduce a proposed quantum circuit optimized for depth. Furthermore, we utilize the estimated cost to evaluate post-quantum security strength of ASCON, employing the relevant evaluation criteria and the latest advancements in research.
The progression of quantum computing is considered a potential threat to traditional cryptography system, highlighting the significance of post-quantum security in cryptographic systems. Regarding symmetric key encryption, the Grover algorithm can approximately halve the search complexity. Despite the absence of fully operational quantum computers at present, the necessity of assessing the security of symmetric key encryption against quantum computing continues to grow.In this paper, we implement the ARIA block cipher in a quantum circuit and compare it with previous research. Our implementation of the ARIA quantum circuit achieves over 92.5% improvement in full depth and over 98.7% improvement in Toffoli depth compared to the implementation proposed in Chauhan et al. Compared to Yang et al.’s implementation, our implementation is improved the full depth by 36.7% and the number of qubits by 8%. Additionally, we analyze the complexity of Grover’s search attack and compare it with NIST criteria. We confirm that ARIA achieves quantum security level 1, 3, and 5 (ARIA-128, 192, and 256, respectively).
Quantum computers can model and solve several problems that have posed challenges for classical super computers, leveraging their natural quantum mechanical characteristics. A large-scale quantum computer is poised to significantly reduce security strength in cryptography. In this context, extensive research has been conducted on quantum cryptanalysis.In this paper, we present optimized quantum circuits for Korean block ciphers, HIGHT and LEA. Our quantum circuits for HIGHT and LEA demonstrate the lowest circuit depth compared to previous results. Specifically, we achieve depth reductions of 48% and 74% for HIGHT and LEA, respectively. We employ multiple novel techniques that effectively reduce the quantum circuit depth with a reasonable increase in qubit count. Based on our depth-optimized quantum circuits for HIGHT and LEA block ciphers, we estimate the lowest quantum attack complexity for Grover’s key search. Our quantum circuit can be utilized for other quantum algorithms, not only for Grover’s algorithm. Furthermore, the optimization methods gathered in this work can be adopted for generic quantum implementations in cryptography.
A quantum computer capable of running the Grover search algorithm, which reduces the complexity of brute-force attacks by a square root, has the potential to undermine the security strength of symmetric-key cryptography and hash functions. Recently, studies on quantum approaches have proposed analyzing potential quantum attacks using the Grover search algorithm in conjunction with optimized quantum circuit implementations for symmetric-key cryptography and hash functions. Analyzing quantum attacks on a cipher (i.e., quantum cryptanalysis) and estimating the necessary quantum resources are related to evaluating post-quantum security for the target cryptography algorithms. In this paper, we revisit quantum implementations of CHAM block cipher, an ultra lightweight cipher, with a focus on optimizing the linear operations in its key schedule. We optimized the linear equations of CHAM as matrices by applying novel optimized decomposition techniques. Using the improved CHAM quantum circuits, we estimate the cost of Grover’s key search and evaluate the post-quantum security strength with further reduced costs.
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).
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.