Lattice enumeration is a standard technique to solve the shortest vector problem (SVP) and the closest vector problem (CVP) on arbitrary lattices by systematically enumerating all lattice points in a bounded region of space (typically an -dimensional parallelepiped or ellipsoid). Interest in lattice enumeration techniques is due primarily to their low memory requirements (linear in the lattice dimension ), and excellent practical performance in moderately low dimension. Within the class of polynomial space algorithms, enumeration methods currently provide the asymptotically fastest algorithms to find exact solutions to SVP and CVP, both in theory and in practice, with worst-case time complexity . Algorithms based on Sieving and Voronoi cell computation provide theoretically faster solutions to SVP and CVP (running in single exponential time ), but at the cost of using exponential space and (in the case of sieving) also randomness.
The running time of enumeration algorithms greatly depends on the quality of the input lattice basis. So, suitably preprocessing the input lattice using a basis reduction algorithm is an essential part of lattice enumeration methods. Lattice enumeration algorithms differ from each other primarily in how the basis is preprocessed before the actual lattice point enumeration is performed. The first works to consider lattice enumeration with a sufficiently strong form of preprocessing to yield good bounds on the running time were
Improved methods for calculating vectors of short length in a lattice, including a complexity analysis
(Fincke & Pohst - Math. Comp. 44, 1985)
Minkowski’s convex body theorem and integer programming
(Kannan - Math. Op. Research 12(3), 1987 / STOC 1983)
The first work (1) suggested to preprocess the lattice basis using the (polynomial time) LLL lattice reduction algorithm, which leads to running time for enumeration. Kannan (2) proposed a much more involved preprocessing method, which makes recursive calls to the enumeration algorithm in lower dimension, and decreases the (total) asymptotic running time to . An optimal (worst-case) analysis of Kannan’s algorithm is provided in
which shows that (up to lower order terms) Kannan’s algorithm solves SVP in time . However, due to its substantial (exponential time) preprocessing overhead, Kannan’s algorithm is not competitive with asymptotically inferior methods (like (1) and variants based on polynomial time basis reduction) for all reasonably practical values of the lattice dimension . Recently, practical variants of Kannan’s algorithm were introduced in
which achieves asymptotic running time (and for SVP) similar to Kannan’s algorithm, but at the cost of much lighter preprocessing, making the algorithm competitive with simpler enumeration methods already in moderately low dimension.
On the practical side, efficient implementation of enumeration algorithms makes extensive use of floating point arithmetics, which can be rather tricky due to rounding errors and precision issues. For a detailed analysis of SVP enumeration with floating point arithmetics see
whose algorithms are implemented in the fplll library.
Beside preprocessing the input lattice basis, two widely used methods to improve the performance of lattice enumeration algorithms in practice are
While these methods are not known to lead to provable asymptotic improvements in the running time, they can be extremely effective in practice. State of the art enumeration strategies and pruning methods are described in
Lattice basis reduction - Improved practical algorithms and solving subset sum problems
(Schnorr & Euchner - Math. Prog. 1994 / FCT 1991)
Lattice Enumeration using Extreme Pruning
(Gama, Nguyen & Regev - Eurocrypt 2010)
For a survey and experimental comparison of different enumeration strategies, see
A fast and robust (sequential) implementation of lattice enumeration algorithms is available as part of the fplll C/C++ library and command line programs. Another popular implementation is the NTL C++ library. Several papers investigate the parallel implementation of lattice enumeration algorithms.
Parallel enumeration of shortest lattice vectors
(Dagdelen & Schneider - EuroPar 2010) [ePrint]
Parallel shortest lattice vector enumeration on graphics cards
(Hermans, Schneider, Buchmann, Vercauteren & Preneel - Africacrypt 2010) [ePrint]. Code: GPU-ENUM
Extreme enumeration on GPU and in clouds - How many dollars you need to break SVP challenges
(Kuo, Schneider, Dagdelen, Reichelt, Buchmann, Cheng & Yang - CHES 2011)
Lattice Point Enumeration on Block Reduced Bases
(Walter - ICITS 2015) ePrint
Solving BDD by Enumeration: An Update
(Liu, Nguyen - CTRSA 2013)
Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices
(Blömer - ICALP 2000)
On the complexity of decoding lattices using the Korkin-Zolotarev reduced basis
(Banihashemi & Khandani - IEEE TIT 1998)