Paper 2014/569

Fast Lattice Point Enumeration with Minimal Overhead

Daniele Micciancio and Michael Walter

Abstract

Enumeration algorithms are the best currently known methods to solve lattice problems, both in theory (within the class of polynomial space algorithms), and in practice (where they are routinely used to evaluate the concrete security of lattice cryptography). However, there is an uncomfortable gap between our theoretical understanding and practical performance of lattice point enumeration algorithms. The algorithms typically used in practice have worst-case asymptotic running time $2^{O(n^2)}$, but perform extremely well in practice, at least for all values of the lattice dimension for which experimentation is feasible. At the same time, theoretical algorithms (Kannan, Mathematics of Operation Research 12(3):415-440, 1987) are asymptotically superior (achieving $2^{O(n \log n)}$ running time), but they are never used in practice because they incur a substantial overhead that makes them uncompetitive for all reasonable values of the lattice dimension $n$. This gap is especially troublesome when algorithms are run in practice to evaluate the concrete security of a cryptosystem, and then experimental results are extrapolated to much larger dimension where solving lattice problems is computationally infeasible. We introduce a new class of (polynomial space) lattice enumeration algorithms that simultaneously achieve asymptotic efficiency (meeting the theoretical $n^{O(n)} = 2^{O(n \log n)}$ time bound) and practicality, matching or surpassing the performance of practical algorithms already in moderately low dimension. Key technical contributions that allow us to achieve this result are a new analysis technique that allows us to greatly reduce the number of recursive calls performed during preprocessing (from super exponential in $n$ to single exponential, or even polynomial in $n$), a new enumeration technique that can be directly applied to projected lattice (basis) vectors, without the need to remove linear dependencies, and a modified block basis reduction method with fast (logarithmic) convergence properties. The last technique is used to obtain a new SVP enumeration procedure with $\tilde O(n^{n/2e})$ running time, matching (even in the constant in the exponent) the optimal worst-case analysis (Hanrot and Stehlë, CRYPTO 2007) of Kannan's theoretical algorithm, but with far superior performance in practice. We complement our theoretical analysis with a comprehensive set of experiments that not only support our practicality claims, but also allow to estimate the cross-over point between different versions of enumeration algorithms, as well as asymptotically faster (but not quite practical) algorithms running in single exponential $2^{O(n)}$ time and space.

Note: Minor fixes in the formulation of Theorem 1 and 2.