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.
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%.
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.
Quantum circuits of arithmetic operations such as addition are needed to implement quantum algorithms in hardware. Quantum circuits based on Clifford+T gates are used as they can be made tolerant to noise. The tradeoff of gaining fault tolerance from using Clifford+T gates and error correcting codes is the high implementation overhead of the T gate. As a result, the T-count performance measure has become important in quantum circuit design. Due to noise, the risk for errors in a quantum circuit computation increases as the number of gate layers (or depth) in the circuit increases. As a result, low depth circuits such as quantum carry lookahead adders (QCLA)s have caught the attention of researchers. This work presents two QCLA designs each optimized with emphasis on T-count or qubit cost respectively. In-place and out-of-place versions of each design are shown. The proposed QCLAs are compared against the existing works in terms of T-count. The proposed QCLAs for out-of-place addition achieve average T gate savings of 54.34% and 37.21%, respectively. The proposed QCLAs for in-place addition achieve average T gate savings of 72.11% and 35.87%
MD5 and SHA-1 are widely studied hash functions in cryptanalysis, owing to their well-structured round functions and historical significance in cryptography. This paper presents improved quantum circuit implementations of MD5 and SHA-1 specifically optimized for quantum cryptanalysis. We reduce the quantum implementation cost of auxiliary functions and eliminate the use of ancilla qubits, while reducing circuit depth (the number of sequential gate layers) by parallelizing multiple additions in the round operations of MD5 and SHA-1. Additionally, the quantum implementations of MD5 and SHA-1 are optimized by considering a fixed input size under the attack scenario. The proposed implementations achieve a 63% improvement in the depth - qubit count metric for MD5 and a 27% improvement for SHA-1 compared to previous works. By providing reduced quantum resources, this work establishes an improved baseline for the quantum cryptanalysis of MD5 and SHA-1. We analyze quantum attacks on MD5 and SHA-1, showing that the preimage attacks require a full depth of 279 and 296 for MD5 and SHA-1, respectively, while the collision attacks require a full depth of 254 and 264. For a realistic evaluation, we also estimate the quantum resources for fault-tolerant quantum computation, including the number of physical qubits and the runtime, to break MD5 and SHA-1.
With the advancement of quantum computing, traditional hash based security structures are increasingly exposed to threats posed by quantum algorithms. In particular, Grover's algorithm enables significantly faster pre-image attacks on hash functions than classical approaches, highlighting the need for circuit-level quantum countermeasures. To break with quantum computer, implementation of quantum circuit for the hash function is essential. However, the existing approaches require too many gates or discard ancilla qubits. In this paper, we propose a reversible quantum circuit for theθoperation in the Keccak algorithm a core component of SHA-3, by explicitly implementing the inverse functionθ−1. The proposed circuit allows for ancilla qubit reuse and achieves a substantial reduction in number of CNOT gates and qubits compare to previous researches. While the depth of our circuit slightly exceeds that of some existing approaches, the compact and modular design of theθoperation provides a solid foundation for further enhancement.
Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qu trits . Past work with qutrits has demonstrated only constant factor improvements, owing to the log 2 (3) binary-to-ternary compression factor. We present a novel technique, intermediate qutrits, to achieve sublinear depth decompositions of the Generalized Toffoli and other arithmetic circuits using no additional ancilla—a significant improvement over linear depth for the best qubit-only equivalents. For example, our Generalized Toffoli construction features a 70× improvement in two-qudit gate count over a qubit-only decomposition. This results in circuit cost reductions for important algorithms like quantum neurons, Grover search, and even Shor’s algorithm. Using a previously developed simulator with near-term noise models, we demonstrate for these models over 90% mean reliability (fidelity) for the Toffoli construction, versus under 30% for the qubit-only baseline. For our other constructions, such as the Incrementer, the A + B adder and the +K adder, we demonstrate the power of intermediate qutrits in producing asymptotic depth improvements with no additional ancilla. Together, these results suggest qutrits offer a promising path toward scaling quantum computation.