Paper 2015/736

Solving LWE via List Decoding

Mingqiang Wang, Xiaoyun Wang, Kunxian Xia, and Jincheng Zhuang

Abstract

Learning with errors (LWE) was introduced by Regev in 2005, which enjoys attractive worst-case hardness properties. It has served as the foundation for a variety of cryptographic schemes. There are two main types of attacks against LWE: one for the decision version of LWE, the other for the search version of LWE. In this paper, we apply the list decoding method to solve search version of LWE. Our algorithm runs in probabilistic polynomial time and results in specific security estimates for a large range of parameters. To our knowledge, it is the first time to apply the list decoding method to recover the key of LWE. Our algorithm improves Laine and Lauter's result.