Paper 2018/988
On the Hardness of Learning With Errors with Binary Secrets
Daniele Micciancio
Abstract
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 Stehle, STOC 2013), but provide a shorter, more direct proof, and a small improvement in the noise growth of the reduction.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Theory of Computing 14(13):1-17
- DOI
- 10.4086/toc.2018.v014a013
- Keywords
- complexity theorylattice based cryptographyfoundationspseuro-randomness
- Contact author(s)
- daniele @ cs ucsd edu
- History
- 2019-10-04: revised
- 2018-10-18: received
- See all versions
- Short URL
- https://ia.cr/2018/988
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/988,
author = {Daniele Micciancio},
title = {On the Hardness of Learning With Errors with Binary Secrets},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/988},
year = {2018},
doi = {10.4086/toc.2018.v014a013},
url = {https://eprint.iacr.org/2018/988}
}
