## Cryptology ePrint Archive: Report 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 algorithm for binary-LWE that 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 conclusions are that binary-LWE is easier than general LWE. We give experimental results that will be of help when choosing parameters for binary-LWE to achieve certain security levels.

**Category / Keywords: **public-key cryptography / learning with errors, closest vector problem

**Date: **received 11 Dec 2013

**Contact author: **S Galbraith at math auckland ac nz

**Available format(s): **PDF | BibTeX Citation

**Version: **20131216:191745 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]