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,2⟩}$ whose coefficients are binary numbers, 1 or -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$, but an $(n-1)$-degree polynomial encoding $n$ secret coefficients, where each coefficient is a randomly picked binary number in $\{0,1\}$ (denoted as $S\underset{}{\overset{\$}{\leftarrow }}{R}_{⟨n,2⟩}$).