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 attackslearning with errorsclosest 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2013/839}},
      url = {https://eprint.iacr.org/2013/839}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.