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.Category / Keywords: LWE, Hidden Number Problem, key recovery, lattice-based cryptography Date: received 28 Feb 2015, last revised 3 Feb 2016 Contact author: kim laine at gmail com Available format(s): PDF | BibTeX Citation Note: Minor typos fixed. Version: 20160203:171126 (All versions of this report) Short URL: ia.cr/2015/176 Discussion forum: Show discussion | Start new discussion