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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2018/988}},
      url = {https://eprint.iacr.org/2018/988}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.