IACR News item: 01 March 2015
Kim Laine, Kristin Lauter
ePrint ReportTwo main types of attacks are already known for LWE: the distinguishing attack [MR] and the decoding attack [LP], which uses the BKZ algorithm. Our key recovery attack is interesting because it 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. 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.
Additional news items may be found on the IACR news page.