GLWE Modulus Switching

GLWE modulus switching is an extension of RLWE modulus switching. The only difference is that while RLWE’s

A

and

S

are a single polynomial each, GLWE’s

A

and

S

are a list of

k

polynomials each. Thus, the same modulus switching technique as RLWE can be applied to GLWE for its

k

polynomials.

Recall that the GLWE cryptosystem (§B-4.2) is comprised of the following components:

$⟨$ Summary C-4.5 $⟩$ GLWE Modulus Switching

Given a GLWE ciphertext $({A}_{i = 0}^{k - 1}, B)$ where $B = \vec{A} \cdot \vec{S} + Δ M + E mod q$ and $M \in R_{⟨ n, q ⟩}$ , the modulus switch of the ciphertext from $q$ to $\hat{q}$ is equivalent to updating $({A}_{i = 0}^{k - 1}, B)$ to $({\hat{A}}_{i = 0}^{k - 1}, \hat{B})$ as follows:

$\hat{A_{i}} = {\hat{a}}_{i, 0} + {\hat{a}}_{i, 1} X + {\hat{a}}_{i, 2} X^{2} + \dots + {\hat{a}}_{i, n - 1} X^{n - 1}$ , where each ${\hat{a}}_{i, j} = ⌈ a_{i, j} \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$

$\hat{B} = {\hat{b}}_{0} + {\hat{b}}_{1} X + {\hat{b}}_{2} X^{2} + \dots + {\hat{b}}_{n - 1} X^{n - 1}$ , where each ${\hat{b}}_{j} = ⌈ b_{j} \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$

${𝖦𝖫𝖶𝖤}_{S, σ} (\hat{Δ} M + \hat{E} + E^{⟨ 𝜖_{𝑎𝑙𝑙} ⟩}) = ({\hat{A}}_{i = 0}^{k - 1}, \hat{B}) \in R_{⟨ n, \hat{q} ⟩}^{k + 1}$

The above update effectively changes $E$ and $Δ$ as follows:

$\hat{E} = {\hat{e}}_{0} + {\hat{e}}_{1} X + {\hat{e}}_{2} X^{2} + \dots + {\hat{e}}_{n - 1} X^{n - 1}$ , where each ${\hat{e}}_{j} = ⌈ e_{j} \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$

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

Meanwhile, $\vec{S}$ and $M$ stay the same as before.

The proof is similar to that of RLWE modulus switching. The modulus-switched GLWE ciphertext’s culminating rounding drift error for each

j

-th polynomial coefficient in its congruence relationship (i.e.,

B = \sum_{i = 0}^{k - 1} A_{i} \cdot S_{i} + Δ M + E

) is as follows:

𝜖_{j, 𝑎𝑙𝑙} = 𝜖_{b_{j}} - 𝜖_{e_{j}} - \sum_{l = 0}^{k - 1} \sum_{i = 0}^{j} (𝜖_{a_{l, j - i}} \cdot s_{l, i}) + \sum_{l = 0}^{k - 1} \sum_{i = j + 1}^{n - 1} (𝜖_{a_{l, n + j - i}} \cdot s_{l, i})

▹

derived from the proof step 4 of Summary C-4.4:

𝜖_{𝑎𝑙𝑙} = 𝜖_{b_{j}} - 𝜖_{e_{j}} - \sum_{i = 0}^{j} (𝜖_{a_{j - i}} s_{i}) + \sum_{i = j + 1}^{n - 1} (𝜖_{a_{n + j - i}} s_{i})

Note that GLWE’s modulus switching can have a bigger rounding drift error (about

k

times) than that of RLWE’s modulus switching. However, in the long run, the error remains relatively small to the ciphertext modulus, because the rounding errors are independent and uniform and their sum grows slowly (central limit theorem) relative to the modulus.

C-4.5 GLWE Modulus Switching