1

I'm trying to understand the structure of Rings used in Ring-LWE based on Chris Peikert's Decade of Lattice Based Cryptography paper. The paper says that $$R := \mathbb{Z}[x]\big /\langle f(x) \rangle$$ and clearly for this to make sense, $f(x) \in \mathbb{Z}[x]$. But then $R_q$ is defined as $$R_q := R\big / qR \stackrel{?}{=} \mathbb{Z}_q[x]\big / \langle f(x) \rangle$$

So my question is which ring does $f(x)$ in the second equation come from? That is, is $f(x) \in \mathbb{Z}_q[x]$ in the second equation, or is there some other interpretation of $f(x)$ in the definition of $R_q$?

To take a concrete example, if $$f(x) = x^4 + 31 \in \mathbb{Z}[x]$$ and $q = 7$, then is it safe to say that $$ R = \mathbb{Z}[x]\big / \langle x^4 + 31 \rangle $$ and $$ R_q = \mathbb{Z}_7[x]\big / \langle x^4 + 3 \rangle$$ since $31 \equiv 3 \mod 7$.

I somehow find the notion used in cryptography extremely confusing. For starters, who uses $\mathbb{Z}_q$ to mean $\mathbb{Z}\big /q \mathbb{Z}$?

  • What you reading is the quotient ring They are the same representation of the quotient ring. Left the answer to Chris. – kelalaka Oct 18 '21 at 19:24
  • So is my interpretation that $f(x) \in \mathbb{Z}_q[x]$ for second equation correct? Wouldn't it be better to use $\bar{f(}x)$ in that case, which is standard notation. – Suman Thakur Oct 19 '21 at 05:44
  • 2
    pag27: whose canonical representatives are polynomials of degree less than n with coefficients from some set of canonical representatives of $Z_q$. Yes, polynomial in $Z_q$ – kelalaka Oct 19 '21 at 08:00

0 Answers0