Lattice Decoding Attacks on Binary LWE

Shi Bai; Steven D.  Galbraith

Paper 2013/839

Lattice Decoding Attacks on Binary LWE

Shi Bai and Steven D. Galbraith

Abstract

We consider the binary-LWE problem, which is the learning with errors problem when the entries of the secret vector are chosen from $\{ 0, 1\}$ or $\{ -1, 0, 1 \}$ (and the error vector is sampled from a discrete Gaussian distribution). Our main result is an improved lattice decoding algorithm for binary-LWE which first translates the problem to the inhomogeneous short integer solution (ISIS) problem, and then solves the closest vector problem using a re-scaling of the lattice. We also discuss modulus switching as an approach to the problem. Our conclusion is that binary-LWE is easier than general LWE. We give experimental results and theoretical estimates that can be used to choose parameters for binary-LWE to achieve certain security levels.

Note: Full version of the paper with additional information and discussion.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Minor revision. ACISP 2014
Keywords: lattice decoding attacks learning with errors closest vector problem.
Contact author(s): shih bai @ gmail com
S Galbraith @ math auckland ac nz
History: 2017-02-21: last of 4 revisions; 2013-12-16: received; See all versions
Short URL: https://ia.cr/2013/839
License: CC BY

BibTeX

@misc{cryptoeprint:2013/839,
      author = {Shi Bai and Steven D.  Galbraith},
      title = {Lattice Decoding Attacks on Binary {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/839},
      year = {2013},
      url = {https://eprint.iacr.org/2013/839}
}