### On the Asymptotic Complexity of Solving LWE

Gottfried Herold, 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
LWEBounded Distance DecodingLatticesBKW
Contact author(s)
elena kirshanova @ rub de
History
2015-12-23: revised
See all versions
Short URL
https://ia.cr/2015/1222

CC BY

BibTeX

@misc{cryptoeprint:2015/1222,
author = {Gottfried Herold and Elena Kirshanova and Alexander May},
title = {On the Asymptotic Complexity of Solving LWE},
howpublished = {Cryptology ePrint Archive, Paper 2015/1222},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/1222}},
url = {https://eprint.iacr.org/2015/1222}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.