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

Research output: Contribution to journalArticle

Standard

In: IEEE Transactions on Information Theory, Vol. 65, No. 8, 08.2019, p. 5243-5259.

Research output: Contribution to journalArticle

RIS

TY - JOUR

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

AU - Guo, Qian

AU - Johansson, Thomas

AU - Mårtensson, Erik

AU - Stankovski, Paul

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

KW - LWE

KW - BKW

KW - Coded-BKW

KW - Lattice codes

KW - Lattice sieving

U2 - 10.1109/TIT.2019.2906233

DO - 10.1109/TIT.2019.2906233

M3 - Article

VL - 65

SP - 5243

EP - 5259

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 8

ER -