RNS-based ModRaise: ModRaiseRNS

ModRaise is an operation of raising a ciphertext’s modulus from

q

𝑞𝑏

(where

q ≪ 𝑞𝑏

). We used ModRaise in BFV’s ciphertext-to-ciphertext multiplication (Summary D-2.7.5 in §D-2.7.5) and in CKKS’s modulus bootstrapping (Summary D-3.13.7 in §D-3.13.7). The RNS-based ModRaise operation is designed as follows:

$⟨$ Summary D-5.2 $⟩$ ModRaise_RNS

Input: $(x_{1}, x_{2}, \dots, x_{k}) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}}$ # which represents the big value $x \in ℤ_{q}$

$𝖬𝗈𝖽𝖱𝖺𝗂𝗌𝖾_{𝖱𝖭𝖲} ({x_{i}}_{i = 1}^{k}, q, 𝑞𝑏)$ # where $q$ and $b$ are co-prime

$= 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏_{𝖱𝖭𝖲} ({x_{i}}_{i = 1}^{k}, q, 𝑞𝑏)$

$= (x_{1}, x_{2}, \dots, x_{k}, 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 ({x_{i}}_{i = 1}^{k}, q, b))$

$= (x_{1}, x_{2}, \dots, x_{k}, c_{1}, c_{2}, \dots, c_{l}) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}} \times ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}$

$= (χ_{1}, χ_{2}, \dots, χ_{k + l}) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}} \times ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}$

# which represents the value $χ \in ℤ_{𝑞𝑏}$

The relationship between $χ$ and $x$ is as follows:

$χ \equiv x + u \cdot q mod 𝑞𝑏$ # the noise generated by ModRaise_RNS is $| 𝑢𝑞 |_{𝑞𝑏}$ (where integer $| u | \leq \frac{k}{2} + 1$ )

$χ \equiv x mod q$

Proof.

In §D-5.1, we proved that $x^{'} = \sum_{i = 1}^{k} | x_{i} \cdot z_{i} |_{q_{i}} \cdot y_{i} = x + u \cdot q$ (where integer $| u | \leq \frac{k}{2} + 1$ ). Therefore, the following holds:

$x^{'} \equiv x_{i} mod q_{i}$ for $i \in [1, k]$ # since $x^{'} = x + u \cdot q \equiv x_{i} mod q_{i}$ (as $q_{i}$ divides $q$ , so $x \equiv x_{i} mod q_{i}$ )

$x^{'} \equiv c_{j} mod b_{j}$ for $j \in [1, l]$ # where each $c_{j} = x + 𝑢𝑞 mod b_{j}$

Therefore, $x^{'} mod 𝑞𝑏$ can be represented as the following RNS residues:

$(x_{1}, x_{2}, \dots, x_{k}, c_{1}, c_{2}, \dots, c_{l}) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}} \times ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}$

$= (x_{1}, x_{2}, \dots, x_{k}, 𝖥𝖺𝗌𝗍𝖡𝖢𝗈𝗇𝗏 ({x_{i}}_{i = 1}^{k}, q, b)) \in ℤ_{q_{1}} \times ℤ_{q_{2}} \times \dots \times ℤ_{q_{k}} \times ℤ_{b_{1}} \times ℤ_{b_{2}} \times \dots \times ℤ_{b_{l}}$

Our ideal goal of mod-raising $x \in ℤ_{q}$ from $q \to 𝑞𝑏$ is to derive an RNS vector of $x mod 𝑞𝑏$ . However, the above RNS vector represents $x^{'} mod 𝑞𝑏$ , where $x^{'} = x + 𝑢𝑞$ (with integer $| u | \leq \frac{k}{2} + 1$ ). Therefore, we can interpret the above RNS vector as representing $x mod 𝑞𝑏$ with the additional noise $| 𝑢𝑞 |_{𝑞𝑏}$ . □

D-5.2 RNS-based ModRaise: ModRaiseRNS

D-5.2 RNS-based ModRaise: ModRaise_RNS