A Complete Worst-Case Analysis of Kannan's Shortest Lattice Vector
Algorithm
Guillaume Hanrot and Damien Stehlé
Abstract:
Computing a shortest nonzero vector of a given euclidean lattice and
computing a closest lattice vector to a given target are pervasive
problems in computer science, computational mathematics and
communication theory.
The classical algorithms for these tasks were invented by Ravi Kannan
in 1983 and, though remarkably simple to establish, their complexity
bounds have not been improved for almost thirty years. In the present
paper, we provide a complete worst-case analysis of Kannan's algorithm
for the shortest vector problem. We obtain a new worst-case complexity
upper bound, as well as the first worst-case complexity lower bound,
both of the order of 2^O(d) d^(d/(2e)) (up to polynomial
factors) bit operations, where~$d$ is the rank of the lattice. The
lower bound is obtained by the construction of a probabilistic
algorithm that returns lattice bases on which Kannan's algorithm
requires at least that many operations. We also provide a new
complexity upper bound for Kannan's closest vector algorithm, of the
order of 2^O(d) d^(d/2). To obtain these complexity results,
we prove new bounds on the geometry of lattice bases reduced in the
sense of Hermite-Korkine-Zolotarev, which may be of independent
interest.
Download: pdf.
Homepage