Initial Setup: $\mathrm{\Delta }={\displaystyle \frac{q}{t}}$, $\overrightarrow{s}\underset{}{\overset{\$}{\leftarrow }}{\mathbb{Z}}_2^k$ # where $t$ divides $q$, and each element of $\overrightarrow{s}$ is a 0-degree polynomial

$$

---

Encryption Input: $m\in {\mathbb{Z}}_t$, $\overrightarrow{a}\underset{}{\overset{\$}{\leftarrow }}{\mathbb{Z}}_q^k$, $e\underset{}{\overset{{\chi }_{\sigma }}{\leftarrow }}{\mathbb{Z}}_q$ # each element of $\overrightarrow{a}$ is a 0-degree polynomial

1.

Scale up $m\to \mathrm{\Delta }\cdot m\in {\mathbb{Z}}_q$

2.

Compute $b=\overrightarrow{a}\cdot \overrightarrow{s}+\mathrm{\Delta }m+emodq$

3.

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }(\mathrm{\Delta }m)=(\overrightarrow{a},b)\in {\mathbb{Z}}_q^{k+1}$

---

Decryption Input: $\mathsf{\text{𝖼𝗍}}=(\overrightarrow{a},b)\in {\mathbb{Z}}_q^{k+1}$

1.

${\mathsf{\text{𝖫𝖶𝖤}}}_{\overrightarrow{s},\sigma }^{-1}(\mathsf{\text{𝖼𝗍}})=b-\overrightarrow{a}\cdot \overrightarrow{s}=\mathrm{\Delta }m+e(\mathit{𝑚𝑜𝑑}q)$

2.

Scale down $\lceil {\displaystyle \frac{\mathrm{\Delta }m+e}{\mathrm{\Delta }}}\rfloor =m\in {\mathbb{Z}}_t$ # i.e., modulus switch from $q\to t$

$$

Condition for Correct Decryption:

• The noise $e$ grown over homomorphic operations should be: $e<{\displaystyle \frac{\mathrm{\Delta }}{2}}$.