B-3.1 Setup

Let $t$ the size of plaintext, and $q$ the size of ciphertext, where $t<q$ ($t$ is much smaller than $q$) and $t|q$ (i.e., $t$ divides $q$). Randomly pick a $(n-1)$-degree polynomial $S\in R_{⟨n,q⟩}$ whose coefficients are either $-1,0,1$ as a secret key. Let $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$ the scaling factor of plaintext.

Notice that RLWE’s setup parameters are similar to that of LWE. One difference is that $S$ is not a vector of length $k$ sampled from $\{-1,0,1\}$, but an $(n-1)$-degree polynomial encoding $n$ secret coefficients, where each coefficient is a randomly picked ternary number from $\{-1,0,1\}$ (denoted as $S\underset{}{\overset{\$}{\leftarrow }}{R}_{⟨n,\mathit{\text{𝑡𝑒𝑟𝑛}}⟩}$).