B-3 RLWE Cryptosystem

The RLWE cryptosystem’s ciphertext is a tuple $(A,B)$, where $B=S\cdot A+\mathrm{\Delta }\cdot M+E$. The public key $A$ and the secret key $S$ are $(n-1)$-degree polynomials. The message $M$ and the noise $E$ are an $(n-1)$-degree polynomial, each. Like in LWE, a new public key $A$ is created for each ciphertext, whereas the same secret key $S$ is used for all ciphertexts. In this section, we denote each ciphertext instance as $(A,b)$ instead of $(A^{⟨i⟩},b^{⟨i⟩})$ for simplicity.

In RLWE, all polynomials are computed in the polynomial ring ${\mathbb{Z}}_q[x]∕x^n+1$, where $x^n+1$ is a cyclotomic polynomial with $n=2^f$ for some integer $f$ and the polynomial coefficients are in ${\mathbb{Z}}_q$. Thus, all polynomials in RLWE have the coefficient range ${\mathbb{Z}}_q$ and the maximum polynomial degree of $n-1$. For simplicity, we denote $R_{⟨n,q⟩}={\mathbb{Z}}_q[x]∕(x^n+1)$.