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.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Hidden number problemLWElist decodingmultiplication code
- Contact author(s)
-
wangmingqiang @ sdu edu cn
zhuangjincheng @ iie ac cn - History
- 2015-07-30: withdrawn
- 2015-07-24: received
- See all versions
- Short URL
- https://ia.cr/2015/736
- License
-
CC BY