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.
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.
Extensive research is currently underway to determine the security of existing ciphers in light of the advancements in quantum computing. Against symmetric key cryptography, Grover’s search algorithm is a prominent attack, capable of reducing search costs to the square root. For using Grover’s algorithm, it is imperative to embed the target cipher into a quantum circuit. Even so, this area of research is relatively new; it has garnered significant attention from the research community. In this study, we provide the first estimation of the cost of Grover’s key search attack against the AES-based AEAD schemes Rocca-S, AEGIS-128, and Tiaoxin-346. Our analysis considers circuit depth restrictions specified in NIST’s PQC standardization process. Considering NIST’s maximum depth constraints, We present the overall cost of these attacks using gate count and depth-times-width metrics. We observed that for MAXDEPTH=240 , Rocca-S, AEGIS-128, and Tiaoxin-346 can be retrieved using Grover’s search algorithm with gate count of 1.09 × 2253, 1.14 × 2124, and 1.22 × 2124 respectively. Concerning the current updated values by NIST, these ciphers are secure in terms of the cost of implementing Grover’s attack for key recovery. The quantum circuits of these ciphers are implemented using QISKIT, an open-source software development kit (SDK) designed for working with quantum computers running on the IBM Quantum Experience platform.
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).
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 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.
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.
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.