Rigorous and Efficient Short Lattice Vectors Enumeration
Xavier Pujol and Damien Stehlé
Abstract:
The Kannan-Fincke-Pohst enumeration algorithm for the shortest and
closest lattice vector problems is the keystone of all strong
lattice reduction algorithms and their implementations. In the
context of the fast developing lattice-based cryptography, the
practical security estimates derive from floating-point
implementations of these algorithms. However, these implementations
behave very unexpectedly and make these security estimates
debatable. Among others, numerical stability issues seem to occur
and raise doubts on what is actually computed. We give here the
first results on the numerical behavior of the floating-point
enumeration algorithm. They provide a theoretical and practical
framework for the use of floating-point numbers within strong
reduction algorithms, which could lead to more sensible hardness
estimates.
Download: pdf.
The algorithms described in this article are implemented in
fplll-3.0.
Homepage