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.