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

Lecture notes in computer science

Finding Shortest Vector Using Quantum NV Sieve on Grover

Hyunji Kim, Kyoungbae Jang, Yujin Oh, Woojin Seok, Wonhuck Lee, Kwangil Bae, IlKwon Sohn, Hwajeong Seo

Published Jan 1, 2024• 1 citation
Publisher
DOI
10.1007/978-981-97-1235-9_6

Related papers

On the Practicality of Quantum Sieving Algorithms for the Shortest Vector Problem

João Fernando Doriguello, George Giapitzakis, Alessandro Luongo +1 more

arXiv:2410.13759•Lecture notes in computer science•Jan 1, 2026•1 citation

Solving the Shortest Vector Problem in Lattices Faster Using Quantum Search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

arXiv:1301.6176•Lecture notes in computer science•Jan 1, 2013•27 citations

Quantum nested search for the shortest vector problem

Runxi Cao, Baocang Wang, Juntao Gao

Physical Review A•Jul 3, 2025•0 citations

Efficient variational quantum Korkin-Zolotarev algorithm for solving shortest-vector problems

Xiaokai Hou, Guoqing Zhou, Shan Jin +5 more

Physical Review A•Jan 6, 2026•0 citations

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

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

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

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.

IACR Transactions on Cryptographic Hardware and Embedded Systems•Sep 5, 2025•1 citation
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.
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.