On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving

Qian Guo; Thomas Johansson; Erik Mårtensson; Paul Stankovski Wagner

Paper 2019/009

On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving

Qian Guo, Thomas Johansson, Erik Mårtensson, and Paul Stankovski Wagner

Abstract

The Learning with Errors problem (LWE) has become a central topic in recent cryptographic research. In this paper, we present a new solving algorithm combining important ideas from previous work on improving the Blum-Kalai-Wasserman (BKW) algorithm and ideas from sieving in lattices. The new algorithm is analyzed and demonstrates an improved asymptotic performance. For the Regev parameters $q=n^2$ and noise level $\sigma = n^{1.5}/(\sqrt{2\pi}\log_{2}^{2}n)$, the asymptotic complexity is $2^{0.893n}$ in the standard setting, improving on the previously best known complexity of roughly $2^{0.930n}$. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in ASIACRYPT 2017
Contact author(s): erik martensson @ eit lth se
History: 2019-01-09: received
Short URL: https://ia.cr/2019/009
License: CC BY

BibTeX

@misc{cryptoeprint:2019/009,
      author = {Qian Guo and Thomas Johansson and Erik Mårtensson and Paul Stankovski Wagner},
      title = {On the Asymptotics of Solving the {LWE} Problem Using Coded-{BKW} with Sieving},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/009},
      year = {2019},
      url = {https://eprint.iacr.org/2019/009}
}