Lattice Enumeration Algorithms

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 nn-dimensional parallelepiped or ellipsoid). Interest in lattice enumeration techniques is due primarily to their low memory requirements (linear in the lattice dimension nn), 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 nO(n)n^{O(n)}. Algorithms based on Sieving and Voronoi cell computation provide theoretically faster solutions to SVP and CVP (running in single exponential time 2O(n)2^{O(n)}), but at the cost of using exponential space and (in the case of sieving) also randomness.

Provable algorithms

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

  1. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis
    (Fincke & Pohst - Math. Comp. 44, 1985)

  2. 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 2O(n2)2^{O(n^2)} 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 nO(n)n^{O(n)}. An optimal (worst-case) analysis of Kannan’s algorithm is provided in

  1. Improved analysis of Kannan’s shortest lattice vector algorithm (extended abstract)
    (Hanrot & Stehle - Crypto 2007) [arXiv]

which shows that (up to lower order terms) Kannan’s algorithm solves SVP in time nn/(2e)n^{n/(2e)}. 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 nn. Recently, practical variants of Kannan’s algorithm were introduced in

  1. Fast lattice point enumeration with minimal overhead
    (Micciancio & Walter - SODA 2015) [ePrint]

which achieves asymptotic running time nO(n)n^{O(n)} (and nn/(2e)n^{n/(2e)} 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

  1. Rigorous and efficient short lattice vectors enumeration
    (Pujol & Stehlé - Asiacrypt 2008)

whose algorithms are implemented in the fplll library.

Heuristics

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

  1. Lattice basis reduction - Improved practical algorithms and solving subset sum problems
    (Schnorr & Euchner - Math. Prog. 1994 / FCT 1991)

  2. Lattice Enumeration using Extreme Pruning
    (Gama, Nguyen & Regev - Eurocrypt 2010)

For a survey and experimental comparison of different enumeration strategies, see

  1. Closest point search in lattices
    (Agrell, Eriksson, Vardy & Zeger - IEEE TIT 2002)

Implementations

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.

  1. Parallel enumeration of shortest lattice vectors
    (Dagdelen & Schneider - EuroPar 2010) [ePrint]

  2. Parallel shortest lattice vector enumeration on graphics cards
    (Hermans, Schneider, Buchmann, Vercauteren & Preneel - Africacrypt 2010) [ePrint]. Code: GPU-ENUM

  3. 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)

Other papers

  1. Lattice Point Enumeration on Block Reduced Bases
    (Walter - ICITS 2015) ePrint

  2. Solving BDD by Enumeration: An Update
    (Liu, Nguyen - CTRSA 2013)

  3. Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices
    (Blömer - ICALP 2000)

  4. On the complexity of decoding lattices using the Korkin-Zolotarev reduced basis
    (Banihashemi & Khandani - IEEE TIT 1998)