Cryptology ePrint Archive: Report 2015/1222

On the Asymptotic Complexity of Solving LWE

Gottfried Herold and Elena Kirshanova and Alexander May

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 combinatorial 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 polynomial 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 $2^{\bigO(n)}$ for $n$-dimensional LWE, where we make the constant hidden in the big-$\bigO$ notion explicit as a simple and easy to handle function of all LWE-parameters. In the lattice case this function also depends on the time to compute a BKZ lattice basis with block size $\Theta(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 attacks.

Category / Keywords: LWE, Bounded Distance Decoding, Lattices, BKW

Date: received 21 Dec 2015, last revised 23 Dec 2015

Contact author: elena kirshanova at rub de

Available format(s): PDF | BibTeX Citation

Version: 20151223:213903 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]