This post is based on The Beginner’s Textbook for Fully Homomorphic Encryption by Ronny Ko.
In this post, I provide a summary and review of “II. Post-quantum Cryptography: B-3. RLWE Cryptosystem.”

B-3. RLWE Cryptosystem

1. Key Notations

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 RLWE, all polynomials are computed in the ring: \(R_{n,q} = \mathbb{Z}_q[x] / (x^n + 1)\)

• $x^n + 1$ is a cyclotomic polynomial
• $n = 2^f$ for some integer $f$
• Coefficients are in $\mathbb{Z}_q$

In RLWE, the ciphertext is defined as a tuple $(A, B)$, where \(B = S \cdot A + \Delta \cdot M + E\)

2. Notes

• Each element in $R_{n,q}$ is a polynomial of degree at most $n-1$
• $M$ is often defined in: \(R_t = \mathbb{Z}_t[x]/(x^n + 1)\) and scaled using $\Delta = \frac{q}{t}$

B-3.1 Setup

Let $t$ be the size of the plaintext space, and $q$ the size of the ciphertext space, where $t < q$ and $t \mid q$.

1. Secret Key

Randomly sample a polynomial: \(S \leftarrow R_{n,2}\)

• $S$ is a polynomial of degree at most $n-1$
• Each coefficient is a binary value in ${0,1}$

→ This means $S$ encodes $n$ secret coefficients

2. Scaling Factor

Define the scaling factor: \(\Delta = \left\lfloor \frac{q}{t} \right\rfloor\)

→ This is used to map plaintext from a smaller space into the ciphertext space

3. Relation to LWE

RLWE setup is similar to LWE, with one key difference:

• LWE: \(S \in \mathbb{Z}_2^k \quad (\text{vector})\)

• RLWE: \(S \in R_{n,2} \quad (\text{polynomial})\)

→ Instead of a vector of length $k$,
$S$ is an $(n-1)$-degree polynomial encoding $n$ secret coefficients

B-3.2 Encryption

1. Encryption Steps

1) Suppose we have a plaintext polynomial: \(M \in R_{n,t}\) → coefficients represent the plaintext values

2) Sample a random polynomial: \(A \in_R R_{n,q}\) → This acts as a one-time public component

3) Sample a small noise polynomial: \(E \leftarrow \chi\) → coefficients are small (e.g., Gaussian noise)

4) Scale the plaintext: \(\Delta \cdot M\) → This embeds $M$ into the ciphertext space $R_{n,q}$

👉 Since $M \in R_{n,t}$ and $\Delta = \frac{q}{t}$,

• each coefficient of $M$ is in $[0, t)$
• after scaling:

→ Thus, $\Delta M \in R_{n,q}$

5) Compute the ciphertext: \(B = A \cdot S + \Delta \cdot M + E \;\; \in R_{n,q}\)

6) Final ciphertext: \((A, B)\)

B-3.3 Decryption

1. Decryption Steps

1) Given a ciphertext $(A, B)$, where

2) Remove the secret-dependent term:

3) Recover the scaled message by rounding:

→ Round each coefficient to the nearest multiple of $\Delta$

👉 If each coefficient of $E$ satisfies: \(|e_i| < \frac{\Delta}{2}\)

then: \(\left\lfloor \Delta M + E \right\rceil_{\Delta} = \Delta M\)

4) Recover the plaintext:

→ equivalent to right-shifting each coefficient by $\log_2 \Delta$ bits