Paper 2015/176

Key Recovery for LWE in Polynomial Time

Kim Laine and Kristin Lauter

Abstract

We discuss a higher dimensional generalization of the Hidden Number Problem and generalize the Boneh-Venkatesan method for solving it in polynomial time. We then use this to analyze a key recovery (decoding) attack on LWE which runs in polynomial time using the LLL lattice basis reduction algorithm and Babai's nearest planes method. We prove that success can be guaranteed with overwhelming probability when the error distribution is narrow enough and $q\geq 2^{O(n)}$, where $n$ is the dimension of the secret key. An explicit constant in the exponent is given, but in practice the performance is observed to be significantly better. Our focus is on attacking the search variant of LWE. Known attacks include combinatorial methods, polynomial system solving (Gröbner basis) methods, and lattice reduction methods. Typically the performance of the lattice reduction attacks involves estimating the performance and complexity of BKZ-2.0, which is difficult. Still another option is to attack the decision version of LWE and use the search-to-decision reductions to break the search problem. Our key recovery attack is interesting because it is runs in polynomial time, and yields simple and concrete security estimates for a wide range of parameters depending in a clear and explicit way on the effective approximation factor in the LLL algorithm and in Babai's nearest planes method. We ran the attack for hundreds of LWE instances demonstrating successful key recovery attacks and yielding information about the effective approximation factor as the lattice dimension grows. For example, we successfully recover the secret key for an instance with $n=350$ in about $3.5$ days on a single machine, provided that the modulus is large enough, and the error distribution narrow enough.

Note: Minor typos fixed.