RLWE Modulus Switching

[prev][parent][next]

C-4.4 RLWE Modulus Switching

RLWE modulus switching is similar to LWE modulus switching. Recall that the RLWE cryptosystem (§B-3.2) comprises the following components:

Setup: $Δ = \frac{q}{t}$ , $S = s_{0} + s_{1} X + s_{2} X^{2} + \dots + s_{n - 1} X^{n - 1} \leftarrow_{}^{$} R_{⟨ n, 𝑡𝑒𝑟𝑛 ⟩}$
Encryption Input:
$M \in R_{⟨ n, t ⟩}$
$A = a_{0} + a_{1} X + a_{2} X^{2} + \dots + a_{n - 1} X^{n - 1} \leftarrow_{}^{$} R_{⟨ n, q ⟩}$
$E = e_{0} + e_{1} X + e_{2} X^{2} + \dots + e_{n - 1} X^{n - 1} \leftarrow_{}^{χ_{σ}} R_{⟨ n, q ⟩}$
Encryption: ${𝖱𝖫𝖶𝖤}_{S, σ} (Δ \cdot M + E) = (A, B) \in R_{⟨ n, q ⟩}^{2}$
, where $B = A \cdot S + Δ \cdot M + E = b_{0} + b_{1} X + b_{2} X^{2} + \dots + b_{n - 1} X^{n - 1}$
Decryption: ${𝖱𝖫𝖶𝖤}_{S, σ}^{- 1} (𝖼𝗍) = B - A \cdot S = Δ M + E \in R_{⟨ n, q ⟩}$

RLWE modulus switching is done as follows:

$⟨$ Summary C-4.4 $⟩$ RLWE Modulus Switching

For an RLWE ciphertext $(A, B)$ where $B = 𝐴𝑆 + Δ M + E$ and $M \in R_{⟨ n, q ⟩}$ , modulus switch of the ciphertext from $q$ to $\hat{q}$ is equivalent to updating $(A, B)$ to $(\hat{A}, \hat{B})$ as follows:

$\hat{A} = {\hat{a}}_{0} + {\hat{a}}_{1} X + {\hat{a}}_{2} X^{2} + \dots + {\hat{a}}_{n - 1} X^{n - 1}$ , where each ${\hat{a}}_{i} = ⌈ a_{i} \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}}_{i} = ⌈ b_{i} \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$

${𝖱𝖫𝖶𝖤}_{S, σ} (\hat{Δ} M + \hat{E} + E^{⟨ 𝜖_{𝑎𝑙𝑙} ⟩}) = (\hat{A}, \hat{B}) \in R_{⟨ n, \hat{q} ⟩}^{2}$

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

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

$\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}}_{i} = ⌈ e_{i} \frac{\hat{q}}{q} ⌋ \in ℤ_{\hat{q}}$

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

The proof is similar to that of LWE modulus switching.

Proof

1.

Note the following:

${\hat{b}}_{i} = ⌈ b_{i} \frac{\hat{q}}{q} ⌋ = b_{i} \frac{\hat{q}}{q} + 𝜖_{b_{i}}$ (where $- 0.5 < 𝜖_{b_{i}} < 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}}_{i} = ⌈ e_{i} \frac{\hat{q}}{q} ⌋ = e_{i} \frac{\hat{q}}{q} + 𝜖_{e_{i}}$ (where $- 0.5 < 𝜖_{e_{i}} < 0.5$ )

2.

Note the following:

$B - A \cdot S$

$= (b_{0} + b_{1} X + \dots + b_{n - 1} X^{n - 1}) - (a_{0} + a_{1} X + \dots + a_{n - 1} X^{n - 1}) (s_{0} + s_{1} X + \dots + s_{n - 1} X^{n - 1})$

$= (b_{0} - (\sum_{i = 0}^{0} (a_{0 - i} s_{i}) - \sum_{i = 1}^{n - 1} (a_{n - i} s_{i})))$

$+ (b_{1} - (\sum_{i = 0}^{1} (a_{1 - i} s_{i}) - \sum_{i = 2}^{n - 1} (a_{n + 1 - i} s_{i}))) \cdot X$

$+ (b_{2} - (\sum_{i = 0}^{2} (a_{2 - i} s_{i}) - \sum_{i = 3}^{n - 1} (a_{n + 2 - i} s_{i}))) \cdot X^{2}$

$⋮$

$+ (b_{n - 1} - (\sum_{i = 0}^{n - 1} (a_{n - 1 - i} s_{i}) - \sum_{i = n}^{n - 1} (a_{n + n - 1 - i} s_{i}))) \cdot X^{n - 1}$ $▹$ Grouping the terms by same exponents

$= \sum_{h = 0}^{n - 1} (b_{h} - (\sum_{i = 0}^{h} (a_{h - i} s_{i}) - \sum_{i = h + 1}^{n - 1} (a_{n + h - i} s_{i}))) \cdot X^{h}$

Thus,

$B = \sum_{h = 0}^{n - 1} b_{h} X^{h}$

$A \cdot S = \sum_{h = 0}^{n - 1} (\sum_{i = 0}^{h} (a_{h - i} s_{i}) - \sum_{i = h + 1}^{n - 1} (a_{n + h - i} s_{i})) \cdot X^{h}$

3.

Based on step 2,

$B = A \cdot S + Δ M + E$

$\sum_{h = 0}^{n - 1} b_{h} X^{h} = \sum_{h = 0}^{n - 1} (\sum_{i = 0}^{h} (a_{h - i} s_{i}) - \sum_{i = h + 1}^{n - 1} (a_{n + h - i} s_{i})) \cdot X^{h} + Δ \sum_{h = 0}^{n - 1} m_{h} X^{h} + \sum_{h = 0}^{n - 1} e_{h} X^{h} \in ℤ_{q}$

$\sum_{h = 0}^{n - 1} b_{h} X^{h} = \sum_{h = 0}^{n - 1} (\sum_{i = 0}^{h} (a_{h - i} s_{i}) - \sum_{i = h + 1}^{n - 1} (a_{n + h - i} s_{i})) \cdot X^{h} + Δ \sum_{h = 0}^{n - 1} m_{h} X^{h} + \sum_{h = 0}^{n - 1} e_{h} X^{h} + H \cdot q$

(where modulo $q$ is replaced by adding $H \cdot q$ , an $(n - 1)$ -degree polynomial whose each coefficient $c_{i}$ is some multiple of $q$ )

4.

According to step 1 and 3, for each

j

in

0 \leq j \leq n - 1

:

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

$= (\sum_{i = 0}^{j} (a_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} (a_{n + j - i} s_{i}) + Δ m_{j} + e_{j} + c_{j} \cdot q) \cdot \frac{\hat{q}}{q} + 𝜖_{b_{j}}$

$= \frac{\hat{q}}{q} \sum_{i = 0}^{j} (a_{j - i} s_{i}) - \frac{\hat{q}}{q} \sum_{i = j + 1}^{n - 1} (a_{n + j - i} s_{i}) + \frac{\hat{q}}{q} \cdot Δ m_{j} + \frac{\hat{q}}{q} e_{j} + \frac{\hat{q}}{q} \cdot c_{j} \cdot q + 𝜖_{b_{j}}$

$= \sum_{i = 0}^{j} (\frac{\hat{q}}{q} \cdot a_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} (\frac{\hat{q}}{q} \cdot a_{n + j - i} s_{i}) + \hat{Δ} m_{j} + ({\hat{e}}_{j} - 𝜖_{e_{j}}) + \hat{q} \cdot c_{j} + 𝜖_{b_{j}}$

$= \sum_{i = 0}^{j} (({\hat{a}}_{j - i} - 𝜖_{a_{j - i}}) \cdot s_{i}) - \sum_{i = j + 1}^{n - 1} (({\hat{a}}_{n + j - i} - 𝜖_{a_{n + j - i}}) \cdot s_{i}) + \hat{Δ} m_{j} + ({\hat{e}}_{j} - 𝜖_{e_{j}}) + \hat{q} \cdot c_{j} + 𝜖_{b_{j}}$

$= \sum_{i = 0}^{j} ({\hat{a}}_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} ({\hat{a}}_{n + j - i} s_{i}) - \sum_{i = 0}^{j} (𝜖_{a_{j - i}} s_{i}) + \sum_{i = j + 1}^{n - 1} (𝜖_{a_{n + j - i}} s_{i}) + \hat{Δ} m_{j} + ({\hat{e}}_{j} - 𝜖_{e_{j}}) + \hat{q} \cdot c_{j} + 𝜖_{b_{j}}$

$= (\sum_{i = 0}^{j} ({\hat{a}}_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} ({\hat{a}}_{n + j - i} s_{i})) + \hat{Δ} m_{j} + {\hat{e}}_{j} + (𝜖_{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})) + \hat{q} \cdot c_{j}$

$= (\sum_{i = 0}^{j} ({\hat{a}}_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} ({\hat{a}}_{n + j - i} s_{i})) + \hat{Δ} m_{j} + {\hat{e}}_{j} + 𝜖_{𝑎𝑙𝑙} \in ℤ_{\hat{q}}$

$▹$ where $𝜖_{𝑎𝑙𝑙} = 𝜖_{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}) \approx 0$

5.

To summarize, for each

0 \leq j \leq n - 1

, each polynomial degree coefficient

\hat{b_{j}}

is approximately as follows:

${\hat{b}}_{j} = (\sum_{i = 0}^{j} ({\hat{a}}_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} ({\hat{a}}_{n + j - i} s_{i})) + \hat{Δ} m_{j} + {\hat{e}}_{j} + 𝜖_{𝑎𝑙𝑙}$

$\approx (\sum_{i = 0}^{j} ({\hat{a}}_{j - i} s_{i}) - \sum_{i = j + 1}^{n - 1} ({\hat{a}}_{n + j - i} s_{i})) + \hat{Δ} m_{j} + {\hat{e}}_{j}$

Thus, $(\hat{A}, \hat{B}) = {𝖱𝖫𝖶𝖤}_{S, σ} (\hat{Δ} M + \hat{E} + E^{⟨ 𝜖_{𝑎𝑙𝑙} ⟩})$ , decrypting which will give us $M$ .

□

[prev][parent][next]