Encryption

1.: Suppose we have a plaintext $m \in ℤ_{t}$ to encrypt.
2.: Randomly pick a vector $A \in ℤ_{q}^{k}$ (of length $k$ ) as a one-time public key (denoted as $A \leftarrow_{}^{$} ℤ_{q}^{k}$ ).
3.: Randomly pick a small one-time noise $e \in ℤ_{q}$ sampled from the Gaussian distribution $χ_{σ}$ (denoted as $e \leftarrow_{}^{χ_{σ}} ℤ_{q}$ ).
4.: Scale $m$ by $Δ$ , which is to compute $Δ \cdot m$ . This converts $m \in ℤ_{t}$ into $Δ \cdot m \in ℤ_{q}$ .
5.: Compute $b = A \cdot S + Δ \cdot m + e \in ℤ_{q}$ .

The LWE encryption formula is summarized as follows:

$⟨$ Summary B-2.2 $⟩$ LWE Encryption

Initial Setup: $Δ = \frac{q}{t}$ , $S \leftarrow_{}^{$} ℤ_{2}^{k}$ , where $t$ divides $q$

Encryption Input: $m \in ℤ_{t}$ , $A \leftarrow_{}^{$} ℤ_{q}^{k}$ , $e \leftarrow_{}^{χ_{σ}} ℤ_{q}$