Performance of cryptanalytic quantum search algorithms is mainly inferred from query complexity which hides overhead induced by an implementation. To shed light on quantitative complexity analysis removing hidden factors, we provide a framework for estimating time–space complexity, with carefully accounting for characteristics of target cryptographic functions. Processor and circuit parallelization methods are taken into account, resulting in the time–space trade-off curves in terms of depth and qubit . The method guides how to rank different circuit designs in order of their efficiency. The framework is applied to representative cryptosystems NIST referred to as a guideline for security parameters, reassessing the security strengths of AES and SHA-2.
Performance of cryptanalytic quantum search algorithms is mainly inferred from query complexity which hides overhead induced by an implementation. To shed light on quantitative complexity analysis removing hidden factors, we provide a framework for estimating time–space complexity, with carefully accounting for characteristics of target cryptographic functions. Processor and circuit parallelization methods are taken into account, resulting in the time–space trade-off curves in terms of depth and qubit . The method guides how to rank different circuit designs in order of their efficiency. The framework is applied to representative cryptosystems NIST referred to as a guideline for security parameters, reassessing the security strengths of AES and SHA-2.
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.
NIST(National Institute of Standards and Technology) estimates the Grover key search cost required for symmetric key cryptography as the postquantum security strength. The Grover search algorithm is applicable to key recovery in symmetric key cryptography, and for this, the target encryption process must be implemented as a quantum circuit. In this paper, we present an optimized implementation of Simplified AES as a quantum circuit. Substitution, Mix Columns, and Key Expansion are implemented efficiently, and as a result of resource analysis, qubits, quantum gates, and circuit depth are significantly reduced compared to the previous result.
Quantum algorithms are often represented in terms of quantum circuits operating on ideal (logical) qubits. However, the practical implementation of these algorithms poses significant challenges. Many quantum algorithms require a substantial number of logical qubits, and the inherent susceptibility to errors of quantum computers require quantum error correction. The integration of error correction introduces overhead in terms of both space (physical qubits required) and runtime (how long the algorithm needs to be run for). This paper addresses the complexity of comparing classical and quantum algorithms, primarily stemming from the additional quantum error correction overhead. We propose a comprehensive framework that facilitates a direct and meaningful comparison between classical and quantum algorithms. By acknowledging and addressing the challenges introduced by quantum error correction, our framework aims to provide a clearer understanding of the comparative performance of classical and quantum computing approaches. This work contributes to understanding the practical viability and potential advantages of quantum algorithms in real-world applications. We apply our framework to quantum cryptanalysis, since it is well known that 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. This analysis provides state-of-the art snap-shot estimates of the realistic costs of implementing quantum attacks on these important cryptographic algorithms, assuming quantum fault-tolerance is achieved using surface code methods, and spanning a range of potential error rates. These estimates serve as a guide for gauging the realistic impact of these algorithms and for benchmarking the impact of future advances in quantum algorithms, circuit synthesis and optimization, fault-tolerance methods and physical error rates.
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.
Grover’s search algorithm allows a quantum adversary to find ak-bit secret key of a block cipher by making O(2k/2) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by theT-depth of its circuit implementation and the number of qubits used by the circuit (width). Since the AES S-box is the only component which requiresT-gates in a quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with lowT-depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose three methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular, one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing itsT-depth.
Abstract In this paper we provide a framework for applying classical search and preprocessing to quantum oracles for use with Grover’s quantum search algorithm in order to lower the quantum circuit-complexity of Grover’s algorithm for single-target search problems. This has the effect (for certain problems) of reducing a portion of the polynomial overhead contributed by the implementation cost of quantum oracles and can be used to provide either strict improvements or advantageous trade-offs in circuit-complexity. Our results indicate that it is possible for quantum oracles for certain single-target preimage search problems to reduce the quantum circuit-size from O 2 n / 2 ⋅ m C O(2n/2⋅mC) (where C originates from the cost of implementing the quantum oracle) to O ( 2 n / 2 ⋅ m C ) O(2n/2⋅mC) without the use of quantum ram, whilst also slightly reducing the number of required qubits. This framework captures a previous optimisation of Grover’s algorithm using preprocessing [21] applied to cryptanalysis, providing new asymptotic analysis. We additionally provide insights and asymptotic improvements on recent cryptanalysis [16] of SIKE [14] via Grover’s algorithm, demonstrating that the speedup applies to this attack and impacting upon quantum security estimates [16] incorporated into the SIKE specification [14].