International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 24 July 2015

Mingqiang Wang, Xiaoyun Wang, Kunxian Xia, Jincheng Zhuang
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.