Abstract
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the stateoftheart 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 timememory 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}.
BibTeX  Entry
@InProceedings{aggarwal_et_al:LIPIcs.STACS.2021.4,
author = {Aggarwal, Divesh and Chen, Yanlin and Kumar, Rajendra and Shen, Yixin},
title = {{Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {4:14:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13649},
URN = {urn:nbn:de:0030drops136494},
doi = {10.4230/LIPIcs.STACS.2021.4},
annote = {Keywords: Lattices, Shortest Vector Problem, Discrete Gaussian Sampling, TimeSpace Tradeoff, Quantum computation, Bounded distance decoding}
}
Keywords: 

Lattices, Shortest Vector Problem, Discrete Gaussian Sampling, TimeSpace Tradeoff, Quantum computation, Bounded distance decoding 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 