A Survey on Ring-LWE Cryptography

The Ring Learning-with-Errors problem, proposed by Lyubashevsky, Peikert and Regev in 2010, is a variant of the traditional Learning-with-Errors problem, and is an active research area in lattice based cryptography. It has drawn increased attention due to the important application to constructing homomorphic encryption schemes. The security of RLWE problems relies on the hardness of certain standard problems over ideal lattices. In the first part of the talk, I will review the basics of RLWE problems, the hardness proofs, and major RLWE encryption schemes. Then I will survey different attacks to RLWE, including our new attacks to non-dual RLWE in sub-cyclotomic fields and small error dual RLWE on prime cyclotomic fields. I will end by summarizing the security situation for various RLWE problems. This is joint work with Kristin Lauter and Katherine Stange.