On the Asymptotics of Solving the LWE Problem Using Coded-BKW With Sieving
Qian Guo, Thomas P. Johansson, Erik Mårtensson, Paul Stankovski · IEEE Transactions on Information Theory · 2019
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 = n2and √ noise level σ = n1.5/( 2π log22 n), the asymptotic complexity is 20.893nin the standard setting, improving the previously best known complexity of roughly 20.930n. The newly proposed algorithm also provides asymptotic improvements when a quantum computer is assumed or when the number of samples is limited.