The security of lattice-based cryptography relies on the computational complexity of solving the Shortest Vector Problem (SVP) on a high-dimensional lattice. Due to its efficacy in addressing SVP, lattice-based cryptographic systems have so far used the sieve algorithm to analyze their security. Previous works have analyzed the theoretical complexity improvement of the sieve algorithm in quantum computing environments, noting that Grover’s algorithm provides a quadratic speed-up for search problems. However, these works have solely focused on the theoretical analysis of query complexity, neglecting to present quantum circuit designs for sieves. Quantum circuit design and quantum resource estimation are necessary for practical analysis of the complexity of quantum sieves. Additionally, the cost of quantum error correction must also be considered, as quantum computation has a large number of errors. In this paper, we present quantum circuit designs for the sieve algorithm and provide estimates of the quantum resources required, including the number of gates and their depth. Furthermore, we evaluate the quantum sieve’s impact on the security level of ML-KEM and ML-DSA, comparing it to the classical sieve algorithm. We do this by evaluating the classical processing cost for quantum error correction using these estimates. Our results show that the quantum sieve algorithm does not break ML-KEM and ML-DSA, but it reduces their security level by 15 to 27 bits compared to the classical sieve.
The security of lattice-based cryptography relies on the computational complexity of solving the Shortest Vector Problem (SVP) on a high-dimensional lattice. Due to its efficacy in addressing SVP, lattice-based cryptographic systems have so far used the sieve algorithm to analyze their security. Previous works have analyzed the theoretical complexity improvement of the sieve algorithm in quantum computing environments, noting that Grover’s algorithm provides a quadratic speed-up for search problems. However, these works have solely focused on the theoretical analysis of query complexity, neglecting to present quantum circuit designs for sieves. Quantum circuit design and quantum resource estimation are necessary for practical analysis of the complexity of quantum sieves. Additionally, the cost of quantum error correction must also be considered, as quantum computation has a large number of errors. In this paper, we present quantum circuit designs for the sieve algorithm and provide estimates of the quantum resources required, including the number of gates and their depth. Furthermore, we evaluate the quantum sieve’s impact on the security level of ML-KEM and ML-DSA, comparing it to the classical sieve algorithm. We do this by evaluating the classical processing cost for quantum error correction using these estimates. Our results show that the quantum sieve algorithm does not break ML-KEM and ML-DSA, but it reduces their security level by 15 to 27 bits compared to the classical sieve.
This paper presents a concrete quantum implementation and resource estimates for the Grover-assisted Nguyen–Vidick (NV) sieve oracle for solving the Shortest Vector Problem (SVP) in lattice-based cryptography. We focus on optimizing the product of the qubit count and circuit depth for a Grover-assisted quantum sieve by combining an in-place carry-lookahead adder and a quantum carry-save adder. Our oracle reduces circuit depth and achieves an improvement of 20%–77% in the qubit count-T-depth product compared to Cho et al. (CHES’25). Using selected core-SVP dimensions associated with the target lattice-based schemes, including National Institute of Standards and Technology (NIST) standards and Korean Post-Quantum Cryptography (KpqC) algorithms, we estimate quantum resources under the adopted heuristic NV-sieve iteration model. The resulting core-SVP costs cover both the plain NV sieve and the spherical locality-sensitive filtering (LSF) variant, and incorporate memory-access costs from read-only quantum lookup circuits. In accordance with the NIST security criteria, our implementation for the core-SVP yields a circuit depth exceeding the MAXDEPTH upper bound of 296, and its total gate count-depth metric significantly exceeds the NIST post-quantum security thresholds corresponding to all evaluated instances. We further estimate surface-code-based fault-tolerant resources under multiple physical error rates and cycle times. As one of our estimates, solving the core-SVP for ML-KEM-512 (NIST post-quantum security level 1) with LSF and low-depth quantum lookup requires approximately 2113 years using 246 physical qubits under p = 10−4 and a 200 ns cycle time.
Abstract Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems whose security depends on solving the SVP. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed.
The security of efficient post-quantum cryptographic primitives, particularly those based on the Ring Learning With Errors (Ring-LWE) problem, relies fundamentally on the presumed intractability of the Shortest Vector Problem (SVP) over ideal lattices. This monograph investigates the hardness of Ideal-SVP in the presence of quantum adversaries. We rigorously analyze the worst-case to average-case reductions that underpin the security of ideal lattice-based schemes, extending classical Gaussian smoothing arguments to the quantum setting. Specifically, we examine the impact of quantum sieving algorithms and the Quantum Fourier Transform (QFT) on the algebraic structure of number fields. While quantum algorithms provide a quadratic speedup for general lattice sieving, we argue that the additional algebraic structure of ideal lattices does not yield a catastrophic collapse in hardness under current quantum reduction models. We present a synthesis of recent results concerning the lower bounds of quantum query complexity for Ideal-SVP, establishing that for cyclotomic fields of degree n, the problem remains hard up to sub-exponential factors, thereby validating the asymptotic security of structured lattice cryptography.
This thesis studies the security of lattice-based and code-based cryptography, two leading approaches to post-quantum cryptography. Although several lattice-based and code-based schemes have been selected for standardization and deployment, these schemes and their underlying computational problems have received less scrutiny than those they aim to replace. Continued cryptanalysis is therefore essential to build confidence in the security of post-quantum cryptography. The first part of this thesis concerns the classical cryptanalysis of lattice-based cryptography. We provide an algorithm that solves the Short Integer Solution problem in subexponential time for nontrivial parameter regimes. Moreover, we develop a predictive model for analyzing the practical performance of module-BKZ, a module-lattice analog of the BKZ algorithm. The second part considers the quantum cryptanalysis of lattice-based and code-based cryptography, focusing on quantum speedups for sieving algorithms. We present a new quantum algorithm for 3-tuple lattice sieving that yields an improved time-memory trade-off for solving the Shortest Vector Problem. We also introduce quantum algorithms for code sieving and investigate their potential for attacking code-based cryptography. Together, these results provide new insights into the security of lattice-based and code-based cryptography and highlight several directions for future research.
The advent of quantum computing poses a significant existential threat to current public-key cryptographic systems, most notably RSA and Elliptic Curve Cryptography (ECC), which rely on the presumed hardness of integer factorization and discrete logarithm problems. Shor's algorithm, a quantum algorithm, can efficiently solve these problems, rendering classical asymmetric primitives insecure. This paper addresses the imperative need for post-quantum cryptography (PQC) by exploring lattice-based constructs as robust alternatives for asymmetric primitives. We provide a comprehensive overview of the fundamental mathematical problems underlying lattice-based cryptography, such as the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Learning With Errors (LWE), and Ring Learning With Errors (RLWE). The paper surveys prominent lattice-based schemes, including NTRU, CRYSTALS-Kyber, and CRYSTALS-Dilithium, analyzing their security foundations, performance characteristics, and the extent to which they offer a viable "post-quantum RSA." We delve into the methodology of constructing these primitives, discuss their resilience against both classical and quantum attacks, and evaluate their practical implications for key sizes, computational efficiency, and deployment challenges. Our analysis highlights that lattice-based cryptography, particularly the NIST-standardized schemes, presents a strong candidate for securing digital communications in the quantum era, offering provable security rooted in worst-case to average-case reductions for lattice problems.
The lattice-based encryption paradigm (LBE) represents a new security model emphasizing flexible development, high levels of security, and efficient computations. It is now becoming more commonly seen as an alternative to other systems of post-quantum cryptography due to its foundations for both security (i.e., there is a high degree of confidence that lattice-based cryptography is secure) and efficiency with respect to computation. The theoretical basis for this report is related to the difficulty of solving the short vector problem (SVP) and other cryptographic hard problems concerning lattices. The report focuses on the hardness of lattice-based cryptography relative to three sub-components of the theoretical work: the relationship between geometric number theory and lattice-based systems, the application of AI to help determine parameters and the efficiencies of finding new lattice reduction algorithms, and finally estimating the difficulty to solve lattice problems. This report reviews the inherent difficulty of short vector problems (SVPs) and other kinds of SVPs, such as the closest vector problem. The report analyzes how to reduce both the time and space complexities for classical and quantum computing solutions through the discovery of new techniques based upon number-theoretic concepts. The report also discusses a number of examples, including digital signature products, encryption systems and homomorphic encryption systems as primitive constructions of cryptography based on lattices or through the properties of the lattice structures. Finally, based on number-theoretical relationships among complex numbers, the report provides a new theoretical approach to the construction of lattice-based systems and their strength relative to other types of cryptographic systems via the provision of theoretical bounds related to the lengths of lattice basis vectors.As a result of this research into bridging the divide between theoretical and practical cryptography, the results show that lattice-based systems have the capability of providing the strength to withstand quantum attacks. Through this research study, there is an improvement in how we understand mathematically the difficulty of lattices and how to create post-quantum secure cryptographic techniques through the use of lattices...