Encryption

1.: Suppose we have an $(n - 1)$ -degree polynomial $M \in R_{⟨ n, t ⟩}$ whose coefficients represent the plaintext numbers to encrypt.
2.: Randomly pick an $(n - 1)$ -degree polynomial $A \in R_{⟨ n, q ⟩}$ as a one-time public key (denoted as $A \leftarrow_{}^{$} R_{⟨ n, q ⟩}$ ).
3.: Randomly pick a small polynomial $E \in R_{⟨ n, q ⟩}$ as a one-time noise, whose $n$ coefficients are small numbers in $ℤ_{q}$ randomly sampled from the Gaussian distribution $χ_{σ}$ (denoted as $E \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}$ ).
4.: Scale $M$ by $Δ$ , which is to compute $Δ \cdot M$ . This converts $M \in R_{⟨ n, p ⟩}$ into $Δ \cdot M \in R_{⟨ n, q ⟩}$ .
5.: Compute $B = A \cdot S + Δ \cdot M + E mod R_{⟨ n, q ⟩}$ (i.e., reduce the degree by $n$ and the coefficient by modulo $q$ ).
6.: The final ciphertext is $(A, B)$ .

The RLWE encryption formula is summarized as follows:

$⟨$ Summary B-3.2 $⟩$ RLWE Encryption

Initial Setup: $Δ = ⌊ \frac{q}{t} ⌋$ , $S \leftarrow_{}^{$} R_{⟨ n, 2 ⟩}$

Encryption Input: $M \in R_{⟨ n, t ⟩}$ , $A \leftarrow_{}^{$} R_{⟨ n, q ⟩}$ , $E \leftarrow_{}^{χ_{σ}} R_{⟨ n, 2 ⟩}$