Welcome to the resource topic for 2019/009
Title:
On the Asymptotics of Solving the LWE Problem Using Coded-BKW with Sieving
Authors: Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner
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.
ePrint: https://eprint.iacr.org/2019/009
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .