Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IACR Transactions on Cryptographic Hardware and Embedded Systems

Quantum security analysis of Module-LWE PQC based on practical cost estimates

Seong-Min Cho, Changyeol Lee, Seung-Hyun Seo

Published Sep 5, 2025• 3 citations
Publisher

Abstract

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.

DOI
10.46586/tches.v2025.i4.437-462

Related papers

Concrete Quantum Sieve for Shortest Vector Problem With Application to Lattice-Based Cryptography

Hyunji Kim, Kyungbae Jang, Anubhab Baksi +4 more

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.

IEEE Access•Jan 1, 2026•0 citations

Estimates of Implementation Complexity for Quantum Cryptanalysis of Post-Quantum Lattice-Based Cryptosystems

Alexander Olegovich Bakharev

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.

Journal of Applied and Industrial Mathematics•Sep 1, 2023•1 citation

Hardness of the Shortest Vector Problem on Ideal Lattices under Quantum Reductions

Zen Revista, 10 MFC

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.

•Feb 4, 2026•0 citations

From Factoring to Shortest Vector: A Unified Security Framework for Post-Quantum Cryptography

Revista, Zen, MATH, 10

The advent of quantum computing poses an existential threat to contemporary public-key cryptographic systems, which rely on the computational hardness of problems such as integer factorization and discrete logarithms. Shor's algorithm, capable of solving these problems efficiently on a sufficiently powerful quantum computer, necessitates a paradigm shift towards post-quantum cryptography (PQC). This paper proposes a unified security framework that bridges the conceptual gap between traditional number-theoretic hardness assumptions and the lattice-based problems central to PQC. We delve into the foundational mathematical problems, comparing the security arguments of factoring and discrete logarithm problems with the Shortest Vector Problem (SVP) and its variants in lattices. The framework emphasizes a consistent methodology for assessing quantum resistance, facilitating a more holistic understanding of cryptographic security in the post-quantum era. By analyzing the inherent complexities and interconnections of these hard problems, we aim to provide a structured approach to evaluate and design quantum-resistant cryptographic schemes, fostering robust and future-proof digital security infrastructure. This work contributes to the ongoing efforts in PQC standardization by offering a comparative lens for diverse cryptographic primitives.

•Nov 25, 2025•0 citations

Quantum resource estimation for large scale quantum algorithms

Vlad Gheorghiu, Michele Mosca

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.

Future Generation Computer Systems•Aug 12, 2024•25 citations

A Number Theoretic Investigation Of The Hardness Assumptions Underlying The Shortest Vector Problem In Lattice Cryptography

Jitendra Sharma

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...

International Journal on Science and Technology•Mar 31, 2026•0 citations
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.
The advent of quantum computing poses an existential threat to contemporary public-key cryptographic systems, which rely on the computational hardness of problems such as integer factorization and discrete logarithms. Shor's algorithm, capable of solving these problems efficiently on a sufficiently powerful quantum computer, necessitates a paradigm shift towards post-quantum cryptography (PQC). This paper proposes a unified security framework that bridges the conceptual gap between traditional number-theoretic hardness assumptions and the lattice-based problems central to PQC. We delve into the foundational mathematical problems, comparing the security arguments of factoring and discrete logarithm problems with the Shortest Vector Problem (SVP) and its variants in lattices. The framework emphasizes a consistent methodology for assessing quantum resistance, facilitating a more holistic understanding of cryptographic security in the post-quantum era. By analyzing the inherent complexities and interconnections of these hard problems, we aim to provide a structured approach to evaluate and design quantum-resistant cryptographic schemes, fostering robust and future-proof digital security infrastructure. This work contributes to the ongoing efforts in PQC standardization by offering a comparative lens for diverse cryptographic primitives.
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 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...