Paper 2017/258

Pseudorandomness of Ring-LWE for Any Ring and Modulus

Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz

Abstract

We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to the decision version of (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. STOC 2017
Keywords
Learning with Errorslattice-based cryptographyworst-case to average-case reduction
Contact author(s)
noahsd @ gmail com
History
2020-06-06: revised
2017-03-25: received
See all versions
Short URL
https://ia.cr/2017/258
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/258,
      author = {Chris Peikert and Oded Regev and Noah Stephens-Davidowitz},
      title = {Pseudorandomness of Ring-LWE for Any Ring and Modulus},
      howpublished = {Cryptology ePrint Archive, Paper 2017/258},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/258}},
      url = {https://eprint.iacr.org/2017/258}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.