Improved Analysis of Kannan's Shortest Lattice Vector Algorithm (Extended Abstract)

Abstract

The security of lattice-based cryptosystems such as NTRU, GGH and Ajtai-Dwork essentially relies upon the intractability of com- puting a shortest non-zero lattice vector and a closest lattice vector to a given target vector in high dimensions. The best algorithms for these tasks are due to Kannan, and, though remarkably simple, their complex- ity estimates have not been improved since over twenty years. Kannan's algorithm for solving the shortest vector problem (SVP) is in particu- lar crucial in Schnorr's celebrated block reduction algorithm, on which rely the best known generic attacks against the lattice-based encryp- tion schemes mentioned above. In this paper we improve the complexity upper-bounds of Kannan's algorithms. The analysis provides new insight on the practical cost of solving SVP, and helps progressing towards pro- viding meaningful key-sizes.