Paper 2016/310

Coded-BKW: Solving LWE Using Lattice Codes

Qian Guo, Thomas Johansson, and Paul Stankovski

Abstract

In this paper we propose a new algorithm for solving the Learning With Errors (LWE) problem based on the steps of the famous Blum-Kalai-Wasserman (BKW) algorithm. The new idea is to introduce an additional procedure of mapping subvectors into codewords of a lattice code, thereby increasing the amount of positions that can be cancelled in each BKW step. The procedure introduces an additional noise term, but it is shown that by using a sequence of lattice codes with different rates the noise can be kept small. Developed theory shows that the new approach compares favorably to previous methods. It performs particularly well for the binary-LWE case, i.e., when the secret vector is sampled from $(0,1)^*$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in CRYPTO 2015
Keywords
LWEbinary-LWEBKWCoded-BKWLattice codes.
Contact author(s)
fywzguoqian @ gmail com
History
2016-03-18: received
Short URL
https://ia.cr/2016/310
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/310,
      author = {Qian Guo and Thomas Johansson and Paul Stankovski},
      title = {Coded-BKW: Solving LWE Using Lattice Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/310},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/310}},
      url = {https://eprint.iacr.org/2016/310}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.