Paper 2013/839

Lattice Decoding Attacks on Binary LWE

Shi Bai and Steven D. Galbraith


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. ACISP 2014
lattice decoding attackslearning with errorsclosest vector problem.
Contact author(s)
shih bai @ gmail com
S Galbraith @ math auckland ac nz
2017-02-21: last of 4 revisions
2013-12-16: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.