Pseudorandomness of Ring-LWE for Any Ring and Modulus
COM1 Level 2
Video Conference Room, COM1-02-13
Abstract:
The Learning with Errors problem (LWE) has innumerable applications in cryptography, from post-quantum key agreement to fully homomorphic encryption. One of the many benefits of LWE is that it is known to be as hard as certain well-studied worst-case lattice problems. However, LWE has many different parameters and comes in many different flavors, including an important variant known as Ring-LWE that yields very efficient cryptographic constructions. Before this work, there were many different flavors and parameterizations of LWE that were used in practice but were not known to be worst-case hard, and each version of LWE that did enjoy worst-case hardness typically required a specialized reduction.
We give a single reduction that shows worst-case hardness for essentially all versions of LWE that have been considered and matches or improves upon all prior reductions (though our reduction is quantum, and some prior work is classical).
Based on joint work with Chris Peikert and Oded Regev available at https://eprint.iacr.org/2017/258.
Biodata:
Noah Stephens-Davidowitz is a postdoctoral researcher at MIT's computer science department, supervised by Vinod Vaikunthanathan. His research to date has focused mostly on lattices and computational problems on lattices, but he is also interested in theoretical computer science and cryptography more broadly. He received his PhD from NYU's Courant Institute, advised by Professors Oded Regev and Yevgeniy Dodis. Before MIT, he was a postdoc at Princeton's computer science department and a visiting researcher at the Institute for Advanced Study's math department---both as part of the Simons Collaboration on Algorithms and Geometry.