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:
https://lup.lub.lu.se/record/f96b3942-3d41-4ed8-bd8f-64f4b2e7747b
- author
- Guo, Qian
LU
; Johansson, Thomas
LU
; Mårtensson, Erik
LU
and Stankovski, Paul
LU
- organization
- publishing date
- 2019-08
- 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
- 2025-10-14 10:28:13
@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}},
keywords = {{LWE; BKW; Coded-BKW; Lattice codes; Lattice sieving}},
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}},
}