Cryptology ePrint Archive: Report 2017/258

Pseudorandomness of Ring-LWE for Any Ring and Modulus

Chris Peikert and 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.

Category / Keywords: foundations / Learning with Errors, lattice-based cryptography, worst-case to average-case reduction

Original Publication (with minor differences): STOC 2017

Date: received 20 Mar 2017, last revised 6 Jun 2020

Contact author: noahsd at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200606:204914 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]