IACR News item: 22 July 2014
Daniele Micciancio, Michael Walter
ePrint ReportThe 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{\\\'e}, 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.
Additional news items may be found on the IACR news page.