Cryptology ePrint Archive: Report 2015/736

Solving LWE via List Decoding

Mingqiang Wang and Xiaoyun Wang and 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.

Category / Keywords: foundations / Hidden number problem, LWE, list decoding, multiplication code

Date: received 22 Jul 2015, last revised 27 Jul 2015, withdrawn 30 Jul 2015

Contact author: wangmingqiang at sdu edu cn, zhuangjincheng@iie ac cn

Available format(s): (-- withdrawn --)

Version: 20150730:094359 (All versions of this report)

Short URL: ia.cr/2015/736

Discussion forum: Show discussion | Start new discussion