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 $(\vec{A}, B)$ where $B = \vec{A} \cdot \vec{S} + Δ M + E mod q$ and $M \in ℝ_{⟨ n, q ⟩}$ , the modulus switch of the ciphertext from $q$ to $\hat{q}$ is equivalent to updating $(\vec{A}, B)$ to $(\hat{\vec{A}}, \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{A}, \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, they can cancel out and converge to 0 as they are sampled from the

σ

distribution.

C-4.5 GLWE Modulus Switching