2025-01-02
Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding
Publication
Publication
SIAM Journal on Computing , Volume 54 - Issue 2 p. 233- 278
The most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q13n+o(n) time and requires poly(n) ̇ q16n/q2 memory. This tradeoff, which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733-742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285-306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRAM model runs in time 20.667n+o(n). As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909-916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice \BbbZn (\BbbZLIP) that runs in time 20.417n+o(n). Our algorithm requires a QRAM of size 20.147n+o(n), poly(n) qubits and 20.25n classical space.
Additional Metadata | |
---|---|
, , , , , | |
doi.org/10.1137/22M1486959 | |
SIAM Journal on Computing | |
Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
Aggarwal, D., Chen, Y., Kumar, R., & Shen, Y. (2025). Improved classical and quantum algorithms for the shortest vector problem via bounded distance decoding. SIAM Journal on Computing, 54(2), 233–278. doi:10.1137/22M1486959 |