International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 16 December 2013

Shi Bai, Steven D. Galbraith
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.