The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this talk, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. ∙ A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. This tradeoff which ranges roughly from enumeration to sieving, is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. ∙ A quantum algorithm that runs in time 2^{0.9535n+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 [ADRSD15] that has a time and space complexity 2^{n+o(n)}. ∙ 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 [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound of a quantity related to the kissing number of a lattice, which is 2^{0.402n}. In practice this quantity is much smaller and is often 2^o(n) for most lattices. In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.
Yixin Shen is a postdoctoral research assistant in the Information Security Group under the supervision of Martin R. Albrecht. She received her PhD from Université de Paris under the supervision of Frédéric Magniez. Her research focuses on classical and quantum algorithms for lattice-based cryptanalysis.