2026-08-06T03:48:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13649 2024-03-06T10:52:34Z ddc:004 open_access

Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding Aggarwal, Divesh Chen, Yanlin Kumar, Rajendra Shen, Yixin Lattices Shortest Vector Problem Discrete Gaussian Sampling Time-Space Tradeoff Quantum computation Bounded distance decoding 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 q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} 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 that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Divesh Aggarwal and Yanlin Chen and Rajendra Kumar and Yixin Shen 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.4 urn:nbn:de:0030-drops-136494 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.4 eng https://creativecommons.org/licenses/by/4.0/legalcode