Solving the Shortest Lattice Vector Problem in Time 2 2.465n
Xavier Pujol, Damien Stehlé · 2009
Abstract. The Shortest lattice Vector Problem is central in lattice-based cryptography, as well as in many areas of computational mathematics and computer science, such as computational number theory and combinatorial optimisation. We present an algorithm for solving it in time 2 2.465n+o(n) and space 2 1.233n+o(n) , where n is the lattice dimension. This improves the best previously known algorithm, by Micciancio and Voulgaris [SODA 2010], which runs in time 2 3.199n+o(n) and space 2 1.325n+o(n).