Pseudorandomness of Ring-LWE for Any Ring and Modulus

p>Our main result is a quantum polynomial-time reduction from worst-case problems on ideal lattices to the *decision* version of Learning With Errors over Rings (Ring-LWE), for *any number
ring* and *any modulus* that is not too small (relative to the error rate). Such a reduction was previously known for the *search* version of Ring-LWE, but hardness of the decision version—which is typically needed for cryptographic applications—was only known to hold for the special case of Galois number rings, such as cyclotomics.
The new reduction at least matches, and in some cases improves upon, the parameters obtained in prior work for both the search and decision problems.

Our approach also applies to the original Learning With Errors (LWE) problem, yielding a quantum reduction from worst-case problems on general lattices to decision LWE, again matching or improving upon the parameters obtained by all prior reductions.

Joint work with Oded Regev and Noah Stephens-Davidowitz.