Algorithms for the Shortest and Closest Lattice
Guillaume Hanrot, Xavier Pujol and Damien Stehlé
Abstract: We present the state of the art solvers of the Shortest and
Closest Lattice Vector Problems in the Euclidean norm. We recall the
three main families of algorithms for these problems, namely the
algorithm by Micciancio and Voulgaris based on the Voronoi cell
[STOC.10], the Monte-Carlo algorithms derived from the Ajtai, Kumar
and Sivakumar algorithm [STOC.01] and the enumeration algorithms
originally elaborated by Kannan [STOC.83] and Fincke and Pohst
[EUROCAL.83]. We concentrate on the theoretical worst-case complexity
bounds, but also consider some practical facets of these algorithms.
Download (corrected version): pdf.