Lattice Decoding Attacks on Binary LWE

Shi Bai; Steven D.  Galbraith

Paper 2013/839 Original: eprint.iacr.org/2013/839 ↗

Lattice Decoding Attacks on Binary LWE

Shi Bai

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.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2017-02-21: last updated; 2013-12-16: published
Short URL: https://ia.cr/2013/839
License: https://creativecommons.org/licenses/by/4.0/

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}
}