Volume 14 (2018)
Article 13 pp. 1-17
On the Hardness of Learning With Errors with Binary Secrets
Received: September 17, 2017
Revised: October 13, 2018
Published: November 30, 2018
Revised: October 13, 2018
Published: November 30, 2018
Keywords: complexity theory, cryptography, pseudorandomness, lattice, learning, LWE
Categories: complexity theory, cryptography, pseudorandomness, lattice, learning, learning with errors, short
ACM Classification: F.2.2, F.1.3
AMS Classification: 68Q17, 52C07, 11H06
Abstract: [Plain Text Version]
$
$
We give a simple proof that the decisional Learning With Errors (LWE) problem with binary secrets (and an arbitrary polynomial number of samples) is at least as hard as the standard LWE problem (with unrestricted, uniformly random secrets, and a bounded, quasi-linear number of samples). This proves that the binary-secret LWE distribution is pseudorandom, under standard worst-case complexity assumptions on lattice problems. Our results are similar to those proved by Brakerski, Langlois, Peikert, Regev and Stehlé (STOC 2013), but provide a shorter, more direct proof, and a small improvement in the noise growth of the reduction.
Licensed under a Creative Commons Attribution License (CC-BY)