Advanced

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

Guo, Qian LU ; Johansson, Thomas LU ; Mårtensson, Erik LU and Stankovski, Paul LU (2019) In IEEE Transactions on Information Theory 65(8). p.5243-5259
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.
Please use this url to cite or link to this publication:
author
; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
LWE, BKW, Coded-BKW, Lattice codes, Lattice sieving
in
IEEE Transactions on Information Theory
volume
65
issue
8
pages
16 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • scopus:85069469947
ISSN
0018-9448
DOI
10.1109/TIT.2019.2906233
language
English
LU publication?
yes
id
f96b3942-3d41-4ed8-bd8f-64f4b2e7747b
date added to LUP
2018-10-07 17:50:48
date last changed
2020-09-23 07:14:37
@article{f96b3942-3d41-4ed8-bd8f-64f4b2e7747b,
  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.},
  author       = {Guo, Qian and Johansson, Thomas and Mårtensson, Erik and Stankovski, Paul},
  issn         = {0018-9448},
  language     = {eng},
  number       = {8},
  pages        = {5243--5259},
  publisher    = {IEEE - Institute of Electrical and Electronics Engineers Inc.},
  series       = {IEEE Transactions on Information Theory},
  title        = {On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving},
  url          = {http://dx.doi.org/10.1109/TIT.2019.2906233},
  doi          = {10.1109/TIT.2019.2906233},
  volume       = {65},
  year         = {2019},
}