The development of quantum computing technology poses potential threats to the security of existing cryptographic algorithms, making it urgent to develop efficient quantum circuit implementation schemes to support security assessments. To design low-T-depth and efficient quantum circuits for the SM3 and RIPEMD-160 Hash functions, the following methods were employed. For SM3, the overall circuit was optimized by applying low-T-depth quantum adders and reorganizing the quantum components. For RIPEMD-160, a low-T-depth quantum implementation of its Boolean functions was designed, the hierarchical parallel arrangement of its compression function was optimized, and its quantum circuit was constructed for the first time. The results show that the proposed SM3 quantum circuit significantly outperforms existing schemes in terms of T-depth and T-DW-cost, with a T-depth of 4 528. The first-time implemented RIPEMD-160 quantum circuit achieves a T-depth of 4 454. These provide efficient circuit implementation schemes for the security assessment of SM3 and RIPEMD-160 in quantum environments.
The development of quantum computing technology poses potential threats to the security of existing cryptographic algorithms, making it urgent to develop efficient quantum circuit implementation schemes to support security assessments. To design low-T-depth and efficient quantum circuits for the SM3 and RIPEMD-160 Hash functions, the following methods were employed. For SM3, the overall circuit was optimized by applying low-T-depth quantum adders and reorganizing the quantum components. For RIPEMD-160, a low-T-depth quantum implementation of its Boolean functions was designed, the hierarchical parallel arrangement of its compression function was optimized, and its quantum circuit was constructed for the first time. The results show that the proposed SM3 quantum circuit significantly outperforms existing schemes in terms of T-depth and T-DW-cost, with a T-depth of 4 528. The first-time implemented RIPEMD-160 quantum circuit achieves a T-depth of 4 454. These provide efficient circuit implementation schemes for the security assessment of SM3 and RIPEMD-160 in quantum environments.
To address the high T-depth issue in SM3 hash function quantum circuits caused by in-place computation, a low T-depth architecture was proposed. By introducing Wallace tree-based quantum carry-save adders and low-depth full/half adders, the multi-operand modular addition path was compressed to a constant level. Furthermore, allocating extra qubits to store intermediate states eliminated the high T-depth operations required for uncomputing ancilla qubits. Experiments demonstrate that using 5 453 qubits reduced the circuit T-depth from 4 528 to 1 712 and decreased the total T-gate count from 965 632 to 314 112. The proposed scheme provides an efficient approach for evaluating the post-quantum security of symmetric cryptography.
SM3 is a hash algorithm independently developed by China. This work mainly studies the quantum circuit implementation of SM3 based on the Clifford+T gate set, and proposes two quantum implementation structures for optimizing the T-depth and width of the circuit, respectively. For the design of quantum circuits with lower T-depth, this paper implements multiple modulo adders applied in parallel, and designs an implementation of quantum circuits for nonlinear components with lower T-depth by utilizing the QAND gate and its conjugate transpose. Based on this, the paper proposes two quantum circuit implementations of the SM3 according to the out-of-place and in-place structures of the nonlinear component, with T-depths of 7040 and 7136, respectively. Compared with the existing circuit with the lowest T-depth, the proposed circuit reduces the T-depth by 72%. For the design of quantum circuits with lower width, this paper groups the constants and variables in the constant modulo addition step, leading to the implementation of the constant modulo operation based on 32 bits only consumes 11 ancilla qubits when the size of group is 4 or 8. Based on this, the paper proposes a quantum circuit implementation of the SM3 that consumes 779 qubits, including 11 ancilla qubits. Compared with the existing circuit with the least consumption of ancilla qubits, the proposed circuit reduces the consumption of ancilla qubits by 67%.
Quantum computers have the potential to solve a number of hard problems that are believed to be almost impossible to solve by classical computers. This observation has sparked a surge of research to apply quantum algorithms against the cryptographic systems to evaluate its quantum resistance. In assessing the security strength of the cryptographic algorithms against the upcoming quantum threats, it is crucial to precisely estimate the quantum resource requirement (generally in terms of circuit depth and quantum bit count). The National Institute of Standards and Technology by the US government specified five quantum security levels so that the relative quantum strength of a given cipher can be compared to the standard ones. There have been some progress in the NIST-specified quantum security levels for the odd levels (i.e., 1, 3 and 5), following the work of Jaques et al. (Eurocrypt’20). However, levels 2 and 4, which correspond to the quantum collision finding attacks for the SHA-2 and SHA-3 hash functions, quantum attack complexities are arguably not well-studied. This is where our article fits in. In this article, we present novel techniques for optimizing the quantum circuit implementations for SHA-2 and SHA-3 algorithms in all the categories specified by NIST. After that, we evaluate the quantum circuits of target cryptographic hash functions for quantum collision search. Finally, we define the quantum attack complexity for levels 2 and 4, and comment on the security strength of the extended level. We present new concepts to optimize the quantum circuits at the component level and the architecture level.
The advent of quantum computers threatens the security of existing hash functions. In this paper, we confirmed the implementation results of quantum circuits for domestic/international hash functions, LSH, SHA2, SHA3 and SM3, and conducted a comparative analysis. To operate the existing hash function in a quantum computer, it must be implemented as a quantum circuit, and the quantum security strength can be confirmed by estimating the necessary quantum resources. We compared methods of quantum circuit implementation and results of quantum resource estimation in various aspects and discussed ways to meet quantum computer security in the future.
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.
Abstract To perform a quantum brute force attack on a cryptosystem based on Grover's algorithm, it is necessary to implement a quantum circuit of the cryptographic algorithm. Therefore, an efficient quantum circuit design of a given cryptographic algorithm is essential, especially in terms of quantum security analysis, and it is well known that T‐depth should be reduced for time complexity efficiency. In this paper, the authors propose a novel technique to reduce T‐depth (and T‐count) when some quantum circuits located in between two Toffoli‐gates are interchangeable with a controlled phase gate (CP gate), and the authors apply this technique to five types of quantum adders, reducing T‐depth by more than 33%. The authors also present new SHA‐256 quantum circuits which have a critical path with only three quantum adders while the critical paths of quantum circuits in the previous studies consist of seven or 10 quantum adders, and the authors also apply our technique to the proposed SHA‐256 quantum circuits. Four versions of SHA‐256 quantum circuit are presented. Among the previous results, T‐depth of the circuit with the smallest Width (the number of qubits) 801 was approximately 109,104. On the other hand, T‐depth of the proposed SHA‐256 quantum circuit with the Width 797 is 16,055, which is remarkably reduced by about 85%. Another proposed quantum circuit only requires 768 qubits, which is the smallest Width compared to the previous results to the best of our knowledge. Furthermore, one other version is the most time‐efficient circuit with an overall Toffoli‐depth (and T‐depth) that is less than 5000.