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

Research output: Contribution to journalArticle

Bibtex

@article{f96b39423d414ed8bd8f64f4b2e7747b,
title = "On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving",
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.",
keywords = "LWE, BKW, Coded-BKW, Lattice codes, Lattice sieving",
author = "Qian Guo and Thomas Johansson and Erik M{\aa}rtensson and Paul Stankovski",
year = "2019",
month = aug,
doi = "10.1109/TIT.2019.2906233",
language = "English",
volume = "65",
pages = "5243--5259",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}