2011 | OriginalPaper | Chapter
Algorithms for the Shortest and Closest Lattice Vector Problems
Authors : Guillaume Hanrot, Xavier Pujol, Damien Stehlé
Published in: Coding and Cryptology
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.