LWE Modulus Switching

In the LWE cryptosystem, modulus switching is a process of converting an original LWE ciphertext’s modulo domain to a smaller modulo domain. This can be seen as scaling down all components, except for the plaintext

m

and the secret key

S

, in the original LWE ciphertext to a smaller domain. This operation preserves the size and integrity of the original plaintext

m

, while the scaling factor

Δ

gets reduced to a smaller value

\hat{Δ}

and the noise

e

to a smaller (reduced) noise

\hat{e}

(note that noise alteration does not affect the original plaintext

m

, because the noise gets rounded away after decryption, anyway), and

\vec{a}

also gets scaled down to a smaller

\vec{\hat{a}}

. Modulus switching is used for computational efficiency during TFHE’s bootstrapping (which will be discussed in §D-1.8). Modulus switching is also used for implementing the ciphertext-to-ciphertext multiplication algorithm in BGV (§D-2.7) and CKKS (§D-3.5).

The high-level idea of LWE modulus switch is to rescale the congruence relationship of the LWE scheme. LWE’s homomorphic computation algorithms include the following: ciphertext-to-ciphertext addition, ciphertext-to-plaintext addition, ciphertext-to-plaintext multiplication, ciphertext-to-ciphertext multiplication. However, all congruence relationships used in these algorithms are essentially rewritten versions of the following single fundamental congruence relationship:

b = \vec{a} \cdot \vec{s} + Δ m + e mod q

. Thus, modulus switch of an LWE ciphertext from

q \to q^{'}

is equivalent to rescaling the modulo of the above congruence relationship from

q \to q^{'}

Based on this insight, the LWE cryptosystem’s modulus switching from

q \to \hat{q}

(where

q > \hat{q}

) is a process of converting the original LWE ciphertext

{𝖫𝖶𝖤}_{S, σ} (Δ m + e)

as follows:

$⟨$ Summary C-4.1 $⟩$ LWE Modulus Switching

Given an LWE ciphertext $(\vec{a}, b)$ where $b = \vec{a} \cdot \vec{s} + Δ m + e mod q$ and $m \in ℤ_{t}$ , modulus switch of the ciphertext from $q$ to $\hat{q}$ is equivalent to updating $(A, b)$ to $(\vec{\hat{a}}, \hat{b})$ as follows:

$\vec{\hat{a}} = ({\hat{a}}_{0}, {\hat{a}}_{1}, \dots, {\hat{a}}_{k - 1})$ , where each ${\hat{a}}_{i} = ⌈ a \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$ $▹$ $⌈⌋$ means rounding to the nearest integer

$\hat{b} = ⌈ b \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$

${𝖫𝖶𝖤}_{S, σ} (\hat{Δ} m + \hat{e} + 𝜖_{𝑎𝑙𝑙}) = ({\hat{a}}_{0}, {\hat{a}}_{1}, \dots, \hat{b}) \in ℤ_{\hat{q}}^{k + 1}$ $▹$ where $𝜖_{𝑎𝑙𝑙}$ is a small rounding error

The above update effectively changes $\hat{e}$ and $\hat{Δ}$ as follows:

$\hat{e} = ⌈ e \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$ ,

$\hat{Δ} = Δ \frac{\hat{q}}{q}$ $▹$ which should be an integer

Meanwhile, $S$ and $m$ stay the same as before.

Note that in order for

({\hat{a}}_{0}, {\hat{a}}_{1}, \dots, \hat{b}) \in ℤ_{\hat{q}}^{k + 1}

to be a valid LWE ciphertext of

\hat{Δ} m

, we need to prove that the following relationship holds:

\hat{b} = \sum_{i = 0}^{k - 1} {\hat{a}}_{i} \cdot s_{i} + \hat{Δ} m + \hat{e} \in ℤ_{\hat{q}}

Proof.

1.

Note the following:

$\hat{b} = ⌈ b \frac{\hat{q}}{q} ⌋ = b \frac{\hat{q}}{q} + 𝜖_{b}$ (where $- 0.5 < 𝜖_{b} < 0.5$ , a rounding drift error)

$\hat{a_{i}} = ⌈ a_{i} \frac{\hat{q}}{q} ⌋ = a_{i} \frac{\hat{q}}{q} + 𝜖_{a_{i}}$ (where $- 0.5 < 𝜖_{a_{i}} < 0.5$ )

$\hat{e} = ⌈ e \frac{\hat{q}}{q} ⌋ = e \frac{\hat{q}}{q} + 𝜖_{e}$ (where $- 0.5 < 𝜖_{e} < 0.5$ )

2.

Note the following:

$b = \vec{a} \cdot \vec{s} + Δ m + e = \sum_{i = 0}^{k - 1} (a_{i} s_{i}) + Δ m + e \in ℤ_{q}$

$b = \sum_{i = 0}^{k - 1} (a_{i} s_{i}) + Δ m + e + H \cdot q$ (where modulo $q$ is replaced by adding $H \cdot q$ , some multiple of $q$ )

3.

According to step 1 and 2:

$\hat{b} = b \frac{\hat{q}}{q} + 𝜖_{b} \in ℤ_{\hat{q}}$

$= (\sum_{i = 0}^{k - 1} (a_{i} s_{i}) + Δ m + e + H \cdot q) \cdot \frac{\hat{q}}{q} + 𝜖_{b}$

$= \frac{\hat{q}}{q} \cdot \sum_{i = 0}^{k - 1} (a_{i} s_{i}) + \frac{\hat{q}}{q} \cdot Δ m + \frac{\hat{q}}{q} \cdot e + \frac{\hat{q}}{q} \cdot H \cdot q + 𝜖_{b}$

$= \sum_{i = 0}^{k - 1} (\frac{\hat{q}}{q} \cdot a_{i} s_{i}) + \hat{Δ} m + (\hat{e} - 𝜖_{e}) + \hat{q} \cdot H + 𝜖_{b}$

$= \sum_{i = 0}^{k - 1} (({\hat{a}}_{i} - 𝜖_{a_{i}}) \cdot s_{i}) + \hat{Δ} m + \hat{e} - 𝜖_{e} + \hat{q} \cdot H + 𝜖_{b}$

$= \sum_{i = 0}^{k - 1} ({\hat{a}}_{i} s_{i} - 𝜖_{a_{i}} s_{i}) + \hat{Δ} m + \hat{e} - 𝜖_{e} + 𝜖_{b} \in ℤ_{\hat{q}}$

$= \sum_{i = 0}^{k - 1} {\hat{a}}_{i} s_{i} + \hat{Δ} m + (\hat{e} - 𝜖_{e} + 𝜖_{b} - \sum_{i = 0}^{k - 1} 𝜖_{a_{i}} s_{i}) \in ℤ_{\hat{q}}$

$= \sum_{i = 0}^{k - 1} {\hat{a}}_{i} s_{i} + \hat{Δ} m + \hat{e} + 𝜖_{𝑎𝑙𝑙} \in ℤ_{\hat{q}}$ $▹$ where $𝜖_{𝑎𝑙𝑙} = (- 𝜖_{e} + 𝜖_{b} - \sum_{i = 0}^{k - 1} 𝜖_{a_{i}} s_{i})$

The biggest possible value for $𝜖_{𝑎𝑙𝑙}$ is,

$𝜖_{𝑎𝑙𝑙} = | - 0.5 | + | 0.5 | + | - 0.5 \cdot k | = 1 + 0.5 k$

So, LWE modulus switching results in an approximate congruence relationship (§A-13). However, if $\hat{Δ}$ is large enough, $𝜖_{𝑎𝑙𝑙} = 1 + 0.5 k$ will be shifted to the right upon LWE decryption and get eliminated, and finally we can recover the original $m$ . Also, in practice, the term $\sum_{i = 0}^{k - 1} 𝜖_{a_{i}} s_{i}$ would remain small relative to the ciphertext modulus for a sufficiently large $k$ , because each $a_{i}$ is uniformly sampled and $s_{i}$ is also uniformly sampled.

Caution: If $\hat{Δ}$ is not large enough, then $𝜖_{𝑎𝑙𝑙}$ may not get eliminated during decryption and corrupt the plaintext $m$ . Also, if $Δ \to \hat{Δ}$ shrinks too much, then the distance between $\hat{Δ} m$ and $\hat{e}$ would become too narrow and the rounding process of $\hat{e} = ⌈ e \frac{\hat{q}}{q} ⌋$ may end up overlapping the least significant bit of $\hat{Δ} m$ , corrupting the plaintext.

4.

To summarize,

\hat{b}

is approximately as follows:

$\hat{b} = \sum_{i = 0}^{k - 1} {\hat{a}}_{i} s_{i} + \hat{Δ} m + \hat{e} + 𝜖_{𝑎𝑙𝑙} \approx \sum_{i = 0}^{k - 1} {\hat{a}}_{i} s_{i} + \hat{Δ} m + \hat{e} \in ℤ_{\hat{q}}$

Thus, $({\hat{a}}_{0}, {\hat{a}}_{1}, \dots, \hat{b}) = {𝖫𝖶𝖤}_{S, σ} (\hat{Δ} m + \hat{e} + 𝜖_{𝑎𝑙𝑙})$ , decrypting which will give us $m$ .

□

C-4.1 LWE Modulus Switching