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