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 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.
Category / Keywords: lattice decoding attacks, learning with errors, closest vector problem.
Original Publication (with minor differences): ACISP 2014
Date: received 11 Dec 2013, last revised 21 Feb 2017
Contact author: shih bai at gmail com;S Galbraith@math auckland ac nz
Available format(s): PDF | BibTeX Citation
Note: Full version of the paper with additional information and discussion.
Version: 20170221:214547 (All versions of this report)
Short URL: ia.cr/2013/839
[ Cryptology ePrint archive ]