5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ In the power of two cyclotomic case, does the error distributions you mentioned for Ring-LWE and Poly-LWE the same, that is, do the error polynomials for $\mathbb{Z}[X]/(X^n+1)$, $n$ a power of 2, also spherical or are they still distorted? $\endgroup$ – Chito Miranda Jul 2 at 5:39
  • 1
    $\begingroup$ Yes, in that case spherical Gaussian error in the canonical embedding is also spherical in the coefficients, and vice versa. $\endgroup$ – Chris Peikert Jul 2 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.