On the Asymptotic Complexity of Solving LWE.
Gottfried Herold, Elena Kirshanova, Alexander May · 2015
Abstract. We provide for the first time an asymptotic comparison of all known algorithms for the search version of the Learning with Errors (LWE) problem. This includes an analysis of several lattice-based approaches as well as the com-binatorial BKW algorithm. Our analysis of the lattice-based approaches defines a general framework, in which the algorithms of Babai, Lindner-Peikert and several pruning strategies appear as special cases. We show that within this framework, all lattice algorithms achieve the same asymptotic complexity. For the BKW algorithm, we present a refined analysis for the case of only a poly-nomial number of samples via amplification, which allows for a fair comparison with lattice-based approaches. Somewhat surprisingly, such a small number of samples does not make the asymptotic complexity significantly inferior, but only affects the constant in the exponent. As the main result we obtain that both, lattice-based techniques and BKW with a polynomial number of samples, achieve running time 2O(n) for n-dimensional LWE, where we make the constant hidden in the big-O notion explicit as a simple and easy to handle function of all LWE-parameters. In the lattice case this func-tion also depends on the time to compute a BKZ lattice basis with block sizeΘ(n). Thus, from a theoretical perspective our analysis reveals how LWE’s complexity changes as a function of the LWE-parameters, and from a practical perspective our analysis is a useful tool to choose LWE-parameters resistant to all known at-tacks.