B-4.2 Encryption

Suppose we have an $(n-1)$-degree polynomial $M\in R_{⟨n,t⟩}$ whose coefficients represent the plaintext numbers to encrypt.

1.

Randomly pick a list of $k$ $(n-1)$-degree polynomials ${\{A_i\}}_{i=0}^{k-1}\underset{}{\overset{\$}{\leftarrow }}{R}_{⟨n,q⟩}^k$ as a one-time public key.

2.

Randomly pick a small polynomial $E\underset{}{\overset{{\chi }_{\sigma }}{\leftarrow }}{R}_{⟨n,q⟩}$ as a one-time noise, whose $n$ coefficients are small numbers in ${\mathbb{Z}}_q$ randomly sampled from the Gaussian distribution ${\chi }_{\sigma }$.

3.

Scale $M$ by $\mathrm{\Delta }$, which is to compute $\mathrm{\Delta }\cdot M$. This converts $M\in R_{⟨n,t⟩}$ into $\mathrm{\Delta }\cdot M\in R_{⟨n,q⟩}$.

4.

Compute $B=\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i\cdot S_i)+\mathrm{\Delta }\cdot M+E\in R_{⟨n,q⟩}$.

The GLWE encryption formula is summarized as follows: