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.
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.
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 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 rapid advancements in quantum technologies have introduced significant threats to the security of conventional cryptographic systems. In particular, the evaluation of quantum resource requirements—measured in terms of circuit depth and qubit count—has become essential for analyzing the resilience of widely used schemes such as AES and RSA, as well as cryptographic hash functions like SHA-2. At the same time, the widespread adoption of Internet of Things (IoT) applications has increased the exposure to cybersecurity risks, which are further exacerbated by the emerging capabilities of quantum adversaries. To address these challenges, the U.S. National Institute of Standards and Technology (NIST) launched a competition to standardize lightweight hash functions and defined five quantum security levels to assess their robustness. In this work, we conduct a resource analysis of the NIST Lightweight Hash Function finalists against the Grover search algorithm, providing detailed insights into their quantum resistance. The findings contribute to a more comprehensive understanding of the security strength of lightweight hash functions in the post-quantum era.
To build a secure cryptography system in the post-quantum era, one must find the minimum security parameters against quantum attacks by estimating the quantum resources of a fault-tolerant quantum computer. In a fault-tolerant quantum computer, errors must reach an acceptable level for practical uses according to error detection and error correction processes. However, these processes utilize additional quantum resources. As the depth of the quantum circuit increases, the computation time per qubit increases together with the processing errors. Therefore, in terms of errors in quantum circuits, it is a fundamental requirement to reduce the depth by trading off the number of qubits. This paper proposes novel low-depth SHA3 quantum circuit implementations for fault-tolerant quantum computers to reduce errors. The proposed SHA3 quantum circuit was implemented with the aim of optimizing the quantum circuit depth through a trade-off between the number of qubits, the quantum gate, and the quantum depth in each function. Compared to other state-of-art techniques, the proposed method achieved T-depth and full-depth reductions of 30.3% and 80.05%, respectively. We believe that this work will contribute to the establishment of minimum security parameters for SHA3 in the quantum era.
Grover’s search algorithm accelerates the key search on the symmetric key cipher and the pre-image attack on the hash function. To conduct Grover’s search algorithm, the target cipher algorithm should be efficiently implemented in a quantum circuit. Currently, small quantum computers are difficult to operate with large quantum circuits due to limited performance. Therefore, if a large quantum computer that can operate Grover’s algorithm appears, it is expected that a cipher attack will be possible. In this paper, we propose a parallel structure quantum circuit for the Korean hash function standard (i.e., LSH). The proposed quantum circuit designed a parallel operation structure for the message expansion (i.e., MsgExp) function and the mix function, which are the internal structures of the LSH hash function. This approach shows an efficient result for quantum circuit implementation in terms of quantum resources by reducing the depth of the quantum circuit by about 96% through the trade-off of appropriate quantum resources compared to previous work. This result can be a reference for the implementation of a parallel quantum circuit in the future and is expected to advance the attack timing of the search algorithm for Grover’s LSH hash function.
Quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. For attacking symmetric cryptography and hash functions, generic quantum attacks are substantially less powerful than they are for today's public-key cryptography. So security will degrade gradually as quantum computing resources increase. At present, there is a substantial resource overhead due to the cost of fault-tolerant quantum error correction. We provide estimates of this overhead using state-of-the-art methods in quantum fault-tolerance. We use state-of-the-art optimized circuits, though further improvements in their implementation would also reduce the resources needed to implement these attacks. To bound the potential impact of further circuit optimizations we provide cost estimates assuming trivial-cost implementations of these functions. These figures indicate the effective bit-strength of the various symmetric schemes and hash functions based on what we know today (and with various assumptions on the quantum hardware), and frame the various potential improvements that should continue to be tracked. As an example, we also look at the implications for Bitcoin's proof-of-work system. For many of the currently used asymmetric (public-key) cryptographic schemes based on RSA and elliptic curve discrete logarithms, we again provide cost estimates based on the latest advances in cryptanalysis, circuit compilation and quantum fault-tolerance theory. These allow, for example, a direct comparison of the quantum vulnerability of RSA and elliptic curve cryptography for a fixed classical bit strength.