Algorithms for the Shortest and Closest Lattice Vector Problems

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.

Homepage