Abstract:
Despite their popularity,
lattice reduction algorithms remain mysterious cryptanalytical tools.
Though it has been widely reported that they behave better than their proved worst-case theoretical bounds,
no precise assessment has ever been given.
Such an assessment would be very helpful to predict the behaviour of lattice-based attacks,
as well as to select keysizes for lattice-based cryptosystems.
The goal of this paper is to provide such an assessment,
based on extensive experiments performed with the NTL library.
The experiments suggest several conjectures on the worst case
and the actual behaviour of lattice reduction algorithms.
We believe the assessment might also help to design new reduction algorithms overcoming the limitations of current algorithms.
Bibtex:
@inproceedings{GaNg08,
AUTHOR = {Nicolas Gama and Phong Q. Nguyen},
TITLE = {Predicting Lattice Reduction},
booktitle= {Advances in Cryptology -- Proc. Eurocrypt '08},
publisher= {Springer},
series = {Lecture Notes in Computer Science},
year = 2008
}