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.
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.
Many quantum algorithms make use of ancilla, additional qubits used to store temporary information during computation, to reduce the total execution time. Quantum computers will be resource-constrained for years to come so reducing ancilla requirements is crucial. In this work, we give a method to generate ancilia out of idle qubits by placing some in higher-value states, called qudits. We show how to take a circuit with many O(n) ancilla and design an ancilla-free circuit with the same asymptotic depth. Using this, we give a circuit construction for an in-place adder and a constant adder both with O(log n) depth using temporary qudits and no ancilla.
Quantum Computing is making significant advancements toward creating machines capable of implementing quantum algorithms in various fields, such as quantum cryptography, quantum image processing, and optimization. The development of quantum arithmetic circuits for modulo addition is vital for implementing these quantum algorithms. While it is ideal to use quantum circuits based on fault-tolerant gates to overcome noise and decoherence errors, the current Noisy Intermediate Scale Quantum (NISQ) era quantum computers cannot handle the additional computational cost associated with fault-tolerant designs. Our research aims to minimize circuit depth, which can reduce noise and facilitate the implementation of quantum modulo addition circuits on NISQ machines. This work presents quantum carry-lookahead modulo (2n - 1) adder (QCLMA), which is designed to receive two n-bit numbers and perform their addition with an O(log n) depth. Compared to existing work of O(n) depth, our proposed QCLMA reduces the depth and helps increase the noise fidelity. In order to increase error resilience, we also focus on creating a tree structure based Carry path, unlike the chain based Carry path of the current work. We run experiments on Quantum Computer IBM Cairo to evaluate the performance of the proposed QCLMA against the existing work and define Quantum State Fidelity Ratio (QSFR) to quantify the closeness of the correct output to the top output. When compared against existing work, the proposed QCLMA achieves a 47.21% increase in QSFR for 4-qubit modulo addition showcasing its superior noise fidelity.