What is the difference between Poly-LWE and Ring-LWE?

Question

I am often confused by Poly-LWE and Ring-LWE, always thinking that they are different names for the same thing. In some literature, Poly-LWE is a simplified version of Ring-LWE? What is the difference?

Answer 1

One main difference is that in Ring-LWE, the ring $R$ is the full ring of integers $\mathcal{O}_K$ of a number field $K$, whereas in Poly-LWE it is of the form $R=\mathbb{Z}[x]/f(x)$ for some irreducible $f(x)$; this ring is (isomorphic to) an order of the number field $K=\mathbb{Q}(x)/f(x)$, but may not be the full ring of integers.

Another important difference is that in Ring-LWE, the (non-noisy) products $a_i \cdot s \in R^\vee_q$ belong to the dual (fractional) ideal $R^\vee$ of the ring (modulo $q$), whereas in Poly-LWE, all of $a_i, s, a_i \cdot s$ belong to $R_q$. While the latter is technically simpler, there are several advantages that come with using the dual form.

A third important difference is that in Ring-LWE we usually consider error distributions which are essentially spherical in the canonical embedding, whereas in Poly-LWE we usually consider error polynomials whose coefficients are independent small values (e.g., Gaussians)—such error polynomials may be quite “skewed” in the canonical embedding. Again, the latter choice looks technically simpler at first, but in crypto applications there are advantages to the former (especially in conjunction with the “dual” form of Ring-LWE), relating to more tightly controlling the errors as they accumulate.

The two problems can be formally related, up to some blowup and distortion in the error distribution. See https://eprint.iacr.org/2019/878 for the latest information.