"Fast Lattice Point Enumeration with Minimal Overhead"
Michael Walter
(UCSD)
Monday, May 5th, 2014, 2:00 pm
EBU3B, Room 4140
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 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 $2^{O(n \log n)}$ time bound) and practicality, matching or surpassing the performance of practical algorithms already in moderately low dimension. Two 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 superexponential in $n$ to single exponential, or even polynomial in $n$), and a new enumeration technique that can be directly applied to projected lattice (basis) vectors, without the need to remove linear dependencies.
Joint work with Daniele Micciancio.