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

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)5243-5259
Number of pages16
JournalIEEE Transactions on Information Theory
Volume65
Issue number8
DOIs
Publication statusPublished - 2019 Aug

Subject classification (UKÄ)

  • Signal Processing

Free keywords

  • LWE
  • BKW
  • Coded-BKW
  • Lattice codes
  • Lattice sieving

Fingerprint

Dive into the research topics of 'On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving'. Together they form a unique fingerprint.

Cite this