Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Guillaume Hanrot and Damien Stehlé
Abstract:
The security of lattice-based cryptosystems such as NTRU, GGH and
Ajtai-Dwork essentially relies upon the intractability of computing 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
complexity estimates have not been improved since over twenty
years. Kannan's algorithm for solving the shortest vector problem
(SVP) is in particular crucial in Schnorr's celebrated block reduction
algorithm, on which rely the best known generic attacks against the
lattice-based encryption 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 providing meaningful key-sizes.
Download: pdf, old version.
Homepage