Vadim Lyubashevsky, Chris Peikert, and Oded Regev. “On ideal lattices and learning with errors over rings.” In Advances in Cryptology — EUROCRYPT 2010, Lecture Notes in Computer Science, vol. 6110, pp. 1–23. Springer, 2010.

Introduced Ring LWE (RLWE), which restricts LWE samples to a polynomial ring $R_q={\mathbb{Z}}_q[x]/⟨{\Phi }_n(x)⟩$ (typically the $n$-th cyclotomic ring). This yields $O(n\log n)$-size keys (vs. $O(n^2)$ for plain LWE) and admits fast NTT-based arithmetic. The paper also gives a quantum worst-case to average-case reduction from ideal lattice problems (Ideal-SVP) to Ring LWE.

BibTeX

Copy

@Inproceedings{EC:LyuPeiReg10,
  author = {Vadim Lyubashevsky and Chris Peikert and Oded Regev},
  title = {On Ideal Lattices and Learning with Errors over Rings},
  pages = {1--23},
  editor = {Henri Gilbert},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2010},
  volume = {6110},
  series = {Lecture Notes in Computer Science},
  address = {French Riviera},
  month = {may~30~--~jun~3},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2010},
  doi = {10.1007/978-3-642-13190-5_1},
}