Abstract:
Lattice enumeration algorithms are the most basic algorithms for
solving hard lattice problems such as the shortest vector problem
and the closest vector problem, and are often used in public-key cryptanalysis either as
standalone algorithms, or as subroutines in lattice reduction
algorithms.
Here we revisit these fundamental algorithms and show that surprising
exponential speedups can be achieved both in theory and in practice by using
a new technique, which we call \emph{extreme pruning}.
We also provide what is arguably the first sound analysis of pruning,
which was introduced in the 1990s by Schnorr {\em et al.}
Bibtex:
@inproceedings{GNR10,
author = {N. Gama and P. Q. Nguyen and O. Regev},
title = {Lattice Enumeration using Extreme Pruning},
booktitle= "Advances in Cryptology -- Proceedings of EUROCRYPT '10",
publisher= {Springer},
volume = "6110",
series = {LNCS},
year = 2010
}