Electrical Engineering and Computer Science


Theory Seminar

Pseudorandomness of Ring-LWE for Any Ring and Modulus

Chris Peikert


Associate Professor
University of Michigan
 
Friday, March 10, 2017
10:30am - 11:30am
BBB 3725

Add to Google Calendar

About the Event

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.

Additional Information

Sponsor(s): CSE

Open to: Public