Institute of Information Science, Academia Sinica

The hardness of the Learning with Errors (LWE) problem is usually considered solely from a lattice-reduction perspective. While lattice-reduction approaches appear to be most competitive, understanding of running-times for BKZ (and other basis-reduction algorithms) leaves much to be desired. In this talk, we give an outline of the main combinatorial methods for solving the LWE problem. While uncompetitive at present, these methods have the practical advantage that their running-times are relatively straightforward to deduce. We then give an example of an application of such a method to an LWE-type scheme proposed at PKC '12, illustrating that such approaches can perform in the `real world'. Finally, we highlight a connection to the recent result of Brakerski, Langlois, Peikert, Regev and Stehle on the classical hardness of LWE.