B-2.2 Encryption

1.

Suppose we have a plaintext $m\in {\mathbb{Z}}_t$ to encrypt.

2.

Randomly pick a vector $\overrightarrow{a}\in {\mathbb{Z}}_q^k$ (of length $k$) as a one-time random public mask (denoted as $\overrightarrow{a}\underset{}{\overset{\$}{\leftarrow }}{\mathbb{Z}}_q^k$).

3.

Randomly pick a small one-time noise $e\in {\mathbb{Z}}_q$ sampled from the Gaussian distribution ${\chi }_{\sigma }$ (denoted as $e\underset{}{\overset{{\chi }_{\sigma }}{\leftarrow }}{\mathbb{Z}}_q$).

4.

Scale $m$ by $\mathrm{\Delta }$, which is to compute $\mathrm{\Delta }\cdot m$. This converts $m\in {\mathbb{Z}}_t$ into $\mathrm{\Delta }\cdot m\in {\mathbb{Z}}_q$.

5.

Compute $b=\overrightarrow{a}\cdot \overrightarrow{s}+\mathrm{\Delta }\cdot m+e\in {\mathbb{Z}}_q$.

The LWE encryption formula is summarized as follows: