Ring Learning With Errors (Ring-LWE)
Ring Learning With Errors (Ring-LWE) is the algebraic variant of Learning With Errors set in a polynomial ring rather than over plain integer vectors. Each sample is a pair of ring elements, one uniform and one equal to a secret times the first plus a small error, which compresses many scalar LWE equations into a single polynomial equation.
Efficiency from structure
Working in a ring such as Z_q[x]/(x^n + 1) replaces large matrices with polynomials, so keys shrink from quadratic toward linear size and multiplication runs in n log n time using the number-theoretic transform. Lyubashevsky, Peikert, and Regev introduced Ring-LWE in 2010 with a reduction from worst-case problems on ideal lattices (ePrint 2012/230).
The structure tradeoff
The added ring structure restricts the problem to ideal lattices, a narrower class than the general lattices behind plain LWE (Peikert, 2015). No efficient attack exploits this structure today, but the concern motivated Module-LWE, which tunes how much structure a scheme assumes and now backs ML-KEM.
Sources
- On Ideal Lattices and Learning with Errors over Rings (IACR ePrint Archive, 2012)
- A Decade of Lattice Cryptography (IACR ePrint Archive, 2015)
Cite this entry
"Ring Learning With Errors (Ring-LWE)." postquantum.wiki. Updated July 11, 2026. https://postquantum.wiki/ring-lwe@misc{pqwiki-ring-lwe,
title = {Ring Learning With Errors (Ring-LWE)},
howpublished = {\url{https://postquantum.wiki/ring-lwe}},
year = {2026},
note = {postquantum.wiki, updated 2026-07-11}
}