B-4.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 list of $k$ $(n-1)$-degree polynomials as a secret key, where each polynomial coefficient is a randomly picked binary number in $\{0,1\}$ (i.e., ${\{S_i\}}_{i=0}^{k-1}\underset{}{\overset{\$}{\leftarrow }}{R}_{⟨n,2⟩}^k$). Let $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$ the scaling factor of plaintext.

Notice that GLWE’s setup parameters are similar to that of RLWE. One difference is that $S$ is not an $(n-1)$-degree polynomial encoding $n$ secret coefficients, but a list of $k$ such $(n-1)$-degree polynomials encoding total $n\cdot k$ secret coefficients.