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
-
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},
url = {https://eprint.iacr.org/2017/258}
}
