D-5.10 Applying RNS Techniques to FHE Operations

This subsection will explain how the RNS primitives we have learned so far are used to handle FHE operations for RNS-based ciphertexts in BFV, CKKS, and BGV.

D-5.10.1 Addition and Multiplication of Polynomials

In BFV, CKKS, and BGV, ciphertext-to-plaintext addition, ciphertext-to-ciphertext addition, and ciphertext-to-plaintext multiplication are performed by only involving modulo additions and multiplications among polynomial coefficients. Therefore, we can represent each polynomial coefficient as an RNS residue vector and compute coefficient-wise additions and multiplications by using RNS-based addition and multiplication of residues as explained in Summary A-13.1 (§A-13.1). For example, suppose we have the following two polynomials $P^{⟨1⟩}$ and $P^{⟨2⟩}$:

$P^{⟨1⟩}=\underset{a=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{c}_a^{⟨1⟩}\cdot X^a\in R_{⟨n,q⟩}$

$P^{⟨2⟩}=\underset{b=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{c}_b^{⟨2⟩}\cdot X^b\in R_{⟨n,q⟩}$

In the RNS-variant FHE schemes, we express each polynomial’s each coefficient as an RNS residue vector as follows:

$c_a^{⟨1⟩}=(c_{a,1}^{⟨1⟩},c_{a,2}^{⟨1⟩},\cdots ,c_{a,k}^{⟨1⟩})\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$ # for $a\in [0,n-1]$

$c_b^{⟨2⟩}=(c_{b,1}^{⟨2⟩},c_{b,2}^{⟨2⟩},\cdots ,c_{b,k}^{⟨2⟩})\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$ # for $b\in [0,n-1]$

Given the above RNS setup, when we add or multiply two polynomials, each coefficient-to-coefficient addition is computed as element-wise additions of two RNS residue vectors as follows:

$c_a^{⟨1⟩}+c_b^{⟨2⟩}\equiv \underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(c_{a,i}^{⟨1⟩}+c_{b,i}^{⟨2⟩})y_i{z}_{i}modq$ # where $y_i={\displaystyle \frac{q}{q_i}}$, $z_i=|y_i^{-1}{|}_{q_i}$

$⟺(c_{a,1}^{⟨1⟩}+c_{b,1}^{⟨2⟩},c_{a,2}^{⟨1⟩}+c_{b,2}^{⟨2⟩},\cdots ,c_{a,k}^{⟨1⟩}+c_{b,k}^{⟨2⟩})\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$

Similarly, each coefficient-to-coefficient multiplication is computed as element-wise multiplications of two RNS residue vectors as follows:

$c_a^{⟨1⟩}\cdot c_b^{⟨2⟩}\equiv \underset{i=1}{\overset{k}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(c_{a,i}^{⟨1⟩}\cdot c_{b,i}^{⟨2⟩})y_i{z}_{i}modq$

$⟺(c_{a,1}^{⟨1⟩}\cdot c_{b,1}^{⟨2⟩},c_{a,2}^{⟨1⟩}\cdot c_{b,2}^{⟨2⟩},\cdots ,c_{a,k}^{⟨1⟩}\cdot c_{b,k}^{⟨2⟩})\in {\mathbb{Z}}_{q_1}\times {\mathbb{Z}}_{q_2}\times \cdots \times {\mathbb{Z}}_{q_k}$

Using the above isomorphism, we can efficiently compute ciphertext-to-plaintext addition, ciphertext-to-ciphertext addition, and ciphertext-to-plaintext multiplication of big polynomial coefficients (e.g., 1000 bits big) based on small RNS residues (e.g., 30 bits each).

D-5.10.2 Key Switching

In BFV or CKKS, an RNS-based ciphertext’s key-switching operation from $S\to S^{\prime }$ is performed by computing the following formula in RNS vectors:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M)=B+⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S^{\prime },\sigma }^{\beta ,l}(S)⟩$

In the above formula, the computation of $⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S^{\prime },\sigma }^{\beta ,l}(S)⟩$ can be performed by using (Summary D-5.9 in §D-5.9), after which $B$ can be added to it by using regular RNS-based addition.

Similarly, in the case of the BGV, an RNS-based key-switching operation on a ciphertext from $S\to S^{\prime }$ is performed by computing the following in RNS vectors:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(M)=B+⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S^{\prime },\sigma }^{\beta ,l}(S)⟩$

D-5.10.3 Input Slot Rotation

In BFV or CKKS, an RNS-based ciphertext’s input slot rotation is performed by computing the following formulas in RNS vectors:

1.

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S(X^{J(h)}),\sigma }(\mathrm{\Delta }M(X^{J(h)}))=(A(X^{J(h)})$, $B(X^{J(h)}))$ # where $J(h)=5^{h}mod2n$

2.

Key-switch ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S(X^{J(h)}),\sigma }(\mathrm{\Delta }M(X^{J(h)}))$ to ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S(X),\sigma }(\mathrm{\Delta }M(X^{J(h)}))$

Step 1 is equivalent to re-positioning the coefficients within each polynomial and flipping their signs whenever they cross the boundary of the $n$-th degree term. This step can be done with RNS-based coefficients by moving around each set of RNS residue vectors as a whole whenever the coefficient they represent is re-positioned to a new degree term, and flipping the signs of the residues in the same RNS vector altogether whenever their representing coefficient’s sign is to be flipped. Step 2’s RNS-based key switching can be done in the same way as explained in the previous subsection (§D-5.10.2).

Similarly, in BGV, an RNS-based ciphertext’s input slot rotation is performed by computing the following formulas in RNS vectors:

1.

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S(X^{J(h)}),\sigma }(M(X^{J(h)}))=(A(X^{J(h)})$, $B(X^{J(h)}))$ # where $J(h)=5^{h}mod2n$

2.

Key-switch ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S(X^{J(h)}),\sigma }(M(X^{J(h)}))$ to ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S(X),\sigma }(M(X^{J(h)}))$

We can compute the above formulas in RNS by using the same strategy explained for BFV or CKKS.

D-5.10.4 BFV’s Ciphertext-to-Ciphertext Multiplication

BFV’s ciphertext-to-ciphertext multiplication (Summary D-2.7.5 in §D-2.7.5) comprises ModRaise $\to$ polynomial multiplication $\to$ relinearization $\to$ rescaling, where the order of relinearization and rescaling can be swapped. In RNS-based ciphertext-to-ciphertext multiplication, we will swap the order of these two steps. The procedure is as follows: (1) ModRaise_RNS from $q\to \mathit{𝑞𝑏}$; (2) polynomial multiplication; (3) constant multiplication by $t$; (4) ModSwitch from $\mathit{𝑞𝑏}\to b$; (5) FastBConvEx from $b\to q$; and (6) relinearization. Among these, step $3\sim 5$ corresponds to the rescaling operation. We will explain how each of these steps works.

1.

ModRaise_RNS from $q\to \mathit{𝑞𝑏}{b}_{\alpha }$:

Let $b$ be a new RNS base where $b>\mathrm{\Delta }$ so that $\mathit{𝑞𝑏}$ is large enough to prevent a multiplied scaled plaintext in ciphertexts (i.e., ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$) from exceeding its allowed limit (Summary D-2.3 in §D-2.3) during ciphertext-to-ciphertext multiplication. $b_{\alpha }$ is also added for exact fast base conversion to be performed later. Specifically, we mod-raise the modulus of each polynomial coefficient of ciphertexts $(A^{⟨1⟩},B^{⟨1⟩})$ and $(A^{⟨2⟩},B^{⟨2⟩})$ as follows:

$({\widehat{A}}^{⟨1⟩},{\widehat{B}}^{⟨1⟩})=(A^{⟨1⟩}+U_A^{⟨1⟩}q,B^{⟨1⟩}+U_B^{⟨1⟩}q)mod\mathit{𝑞𝑏}{b}_{\alpha }$

$({\widehat{A}}^{⟨2⟩},{\widehat{B}}^{⟨2⟩})=(A^{⟨2⟩}+U_A^{⟨2⟩}q,B^{⟨2⟩}+U_B^{⟨2⟩}q)mod\mathit{𝑞𝑏}{b}_{\alpha }$

$$

, where each coefficient of $U_A^{⟨1⟩},U_B^{⟨1⟩},U_A^{⟨2⟩},U_B^{⟨2⟩}$ is either $\{-1,0,1\}$. Decrypting these two (noisy) ciphertexts with the private key $S$ would give the following outputs:

${\widehat{A}}^{⟨1⟩}\cdot S+{\widehat{B}}^{⟨1⟩}mod\mathit{𝑞𝑏}{b}_{\alpha }$

$=(A^{⟨1⟩}+U_A^{⟨1⟩}q)\cdot S+(B^{⟨1⟩}+U_B^{⟨1⟩}q)mod\mathit{𝑞𝑏}{b}_{\alpha }$

$=A^{⟨1⟩}\cdot S+B^{⟨1⟩}+U_A^{⟨1⟩}q\cdot S+U_B^{⟨1⟩}qmod\mathit{𝑞𝑏}{b}_{\alpha }$

$=\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+U_A^{⟨1⟩}q\cdot S+U_B^{⟨1⟩}q+K^{⟨1⟩}qmod\mathit{𝑞𝑏}{b}_{\alpha }$ # where $+K^{⟨1⟩}q$ is the $q$-overflows of the decryption process

$$

${\widehat{A}}^{⟨2⟩}\cdot S+{\widehat{B}}^{⟨2⟩}mod\mathit{𝑞𝑏}{b}_{\alpha }$

$=(A^{⟨2⟩}+U_A^{⟨2⟩}q)\cdot S+(B^{⟨2⟩}+U_B^{⟨2⟩}q)mod\mathit{𝑞𝑏}{b}_{\alpha }$

$=A^{⟨2⟩}\cdot S+B^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}qmod\mathit{𝑞𝑏}{b}_{\alpha }$

$=\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}qmod\mathit{𝑞𝑏}{b}_{\alpha }$

$$

2.

Polynomial Multiplication:

Compute $({\widehat{B}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩},{\widehat{A}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}+{\widehat{A}}^{⟨2⟩}{B}^{⟨1⟩},{\widehat{A}}^{⟨1⟩}{\widehat{A}}^{⟨2⟩})mod\mathit{𝑞𝑏}{b}_{\alpha }$, whose decryption relation is as follows:

${\widehat{B}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}+({\widehat{A}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}+{\widehat{A}}^{⟨2⟩}{B}^{⟨1⟩})\cdot S+({\widehat{A}}^{⟨1⟩}{\widehat{A}}^{⟨2⟩})\cdot S^{2}mod\mathit{𝑞𝑏}{b}_{\alpha }$

$=({\widehat{A}}^{⟨1⟩}\cdot S+{\widehat{B}}^{⟨1⟩})\cdot ({\widehat{A}}^{⟨2⟩}\cdot S+{\widehat{B}}^{⟨2⟩})mod\mathit{𝑞𝑏}{b}_{\alpha }$

$=(\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+U_A^{⟨1⟩}q\cdot S+U_B^{⟨1⟩}q+K^{⟨1⟩}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}q)mod\mathit{𝑞𝑏}{b}_{\alpha }$

$$

3.

Constant Multiplication by $𝐭$:

Step $3\sim 5$ are equivalent to rescaling the plaintext’s scaling factor from ${\mathrm{\Delta }}^2\to \mathrm{\Delta }$ as well as switching the ciphertext’s modulus from $\mathit{𝑞𝑏}{b}_{\alpha }$ to $q$. In this step, we multiply $t$ to each coefficient of the resulting polynomials from the previous step as follows:

$(t\cdot {\widehat{B}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩},t\cdot {\widehat{A}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}+t\cdot {\widehat{A}}^{⟨2⟩}{B}^{⟨1⟩},t\cdot {\widehat{A}}^{⟨1⟩}{\widehat{A}}^{⟨2⟩})mod\mathit{𝑞𝑏}{b}_{\alpha }$

$$

, which is equivalent to a ciphertext encrypting the following plaintext:

$t\cdot (\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+U_A^{⟨1⟩}q\cdot S+U_B^{⟨1⟩}q+K^{⟨1⟩}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}q)mod\mathit{𝑞𝑏}{b}_{\alpha }$

$$

4.

ModSwitch_RNS from $\mathit{𝑞𝑏}{b}_{\alpha }\to b{b}_{\alpha }$:

We switch the modulus of the ciphertext from $\mathit{𝑞𝑏}$ to $b$ by using ModSwitch_RNS as follows:

$\left(\lceil {\displaystyle \frac{t\cdot {\widehat{B}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}}{q}}\rfloor ,\lceil {\displaystyle \frac{t\cdot {\widehat{A}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}+t\cdot {\widehat{A}}^{⟨2⟩}{B}^{⟨1⟩}}{q}}\rfloor ,\lceil {\displaystyle \frac{t\cdot {\widehat{A}}^{⟨1⟩}{\widehat{A}}^{⟨2⟩}}{q}}\rfloor \right)modb{b}_{\alpha }$

$$

, which is (almost, considering the rounding error) equivalent to a ciphertext encrypting the following plaintext:

$\lceil {\displaystyle \frac{t\cdot (\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}+U_A^{⟨1⟩}q\cdot S+U_B^{⟨1⟩}q+K^{⟨1⟩}q)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}q)}{q}}\rfloor modb{b}_{\alpha }$

$$

$=\lceil (M^{⟨1⟩}+{\displaystyle \frac{t}{q}}\cdot E^{⟨1⟩}+U_A^{⟨1⟩}t\cdot S+U_B^{⟨1⟩}t+K^{⟨1⟩}t+{𝜖}_d)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}q)\rfloor modb{b}_{\alpha }$

# where ${𝜖}_d={\displaystyle \frac{t}{q}}\cdot \mathrm{\Delta }{M}^{⟨1⟩}-M^{⟨1⟩}$ is a rounding error caused by treating ${\displaystyle \frac{q}{t}}\approx \lfloor {\displaystyle \frac{q}{t}}\rfloor =\mathrm{\Delta }$

$$

5.

FastBConvEx_RNS from $b\to q$:

We exactly convert the base of the ciphertext from $b{b}_{\alpha }\to q$ as follows:

$\left(\lceil {\displaystyle \frac{t\cdot {\widehat{B}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}}{q}}\rfloor ,\lceil {\displaystyle \frac{t\cdot {\widehat{A}}^{⟨1⟩}{\widehat{B}}^{⟨2⟩}+t\cdot {\widehat{A}}^{⟨2⟩}{B}^{⟨1⟩}}{q}}\rfloor ,\lceil {\displaystyle \frac{t\cdot {\widehat{A}}^{⟨1⟩}{\widehat{A}}^{⟨2⟩}}{q}}\rfloor \right)modq$

$$

, which is equivalent to a ciphertext encrypting the following plaintext:

$=\lceil (M^{⟨1⟩}+{\displaystyle \frac{t}{q}}\cdot E^{⟨1⟩}+U_A^{⟨1⟩}t\cdot S+U_B^{⟨1⟩}t+K^{⟨1⟩}t+{𝜖}_d)\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}q)\rfloor modq$

$=\lceil \mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+{\displaystyle \frac{t}{q}}\cdot \mathrm{\Delta }{M}^{⟨2⟩}{E}^{⟨1⟩}+U_A^{⟨1⟩}t\mathrm{\Delta }{M}^{⟨2⟩}\cdot S+U_B^{⟨1⟩}t\mathrm{\Delta }{M}^{⟨2⟩}+M^{⟨1⟩}{E}^{⟨2⟩}+{\displaystyle \frac{t}{q}}\cdot E^{⟨1⟩}{E}^{⟨2⟩}$

$+U_A^{⟨1⟩}{E}^{⟨2⟩}t\cdot S+U_B^{⟨1⟩}{E}^{⟨2⟩}t+K^{⟨1⟩}t\mathrm{\Delta }{M}^{⟨2⟩}+K^{⟨1⟩}t{E}^{⟨2⟩}+{𝜖}_d\cdot (\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}+U_A^{⟨2⟩}q\cdot S+U_B^{⟨2⟩}q+K^{⟨2⟩}q)\rfloor modq$

$\approx \mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}modq$ # all other terms are relatively much smaller than $\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}$ in modulo $q$

$$

6.

Relinearization:

Once we have derived the rescaled polynomial triple $(D_0^{\prime },D_1^{\prime },D_2^{\prime })modq$, the final relinearization step is equivalent to deriving the synthetic ciphertexts ${\mathsf{\text{𝖼𝗍}}}_{\alpha }$ and ${\mathsf{\text{𝖼𝗍}}}_{\beta }$ and then computing ${\mathsf{\text{𝖼𝗍}}}_{\alpha }+{\mathsf{\text{𝖼𝗍}}}_{\beta }$. ${\mathsf{\text{𝖼𝗍}}}_{\alpha }$ is simply $(D_0^{\prime },D_1^{\prime })$, and we can derive ${\mathsf{\text{𝖼𝗍}}}_{\beta }={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(D_2\cdot S^2)$ by using the DecompMult_RNS operation (Summary D-5.9 in §D-5.9). The final ciphertext-to-ciphertext addition of ${\mathsf{\text{𝖼𝗍}}}_{\alpha }+{\mathsf{\text{𝖼𝗍}}}_{\beta }$ can be performed by using regular RNS addition.

D-5.10.5 CKKS’s Ciphertext-to-Ciphertext Multiplication

CKKS’s ciphertext-to-ciphertext multiplication (Summary D-3.5.6 in §D-3.5.6) is almost the same as BFV’s, except that CKKS does not need the ModRaise operation in the beginning (because each multiplicative level’s modulus $q_l$ is large enough to hold a multiplied scaled plaintext ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$). Therefore, CKKS’s RNS-based multiplication is the same as BFV’s except that it does not require step 1 (ModRaise), step 3 (constant multiplication by $t$), and step 5 (exact fast base conversion). Since a CKKS ciphertext’s scaling factor $\mathrm{\Delta }$ is approximately the same as the prime modulus factor of each multiplicative level, each ciphertext-to-ciphertext multiplication only needs to perform a modulus switch to a lower level.

D-5.10.6 BGV’s Ciphertext-to-Ciphertext Multiplication

BGV’s ciphertext-to-ciphertext multiplication (Summary D-4.8 in §D-4.8) is almost the same as CKKS’s, except that BGV uses its own modulus switch (${\mathsf{\text{𝖬𝗈𝖽𝖲𝗐𝗂𝗍𝖼𝗁}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖦𝖵}}}$ as described in Summary D-4.7 in §D-4.7) during the rescaling step. Therefore, BGV’s RNS-based ciphertext-to-ciphertext multiplication is the same as CKKS’s, except that ModSwitch_RNS is replaced by ${\mathsf{\text{𝖬𝗈𝖽𝖲𝗐𝗂𝗍𝖼𝗁}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖦𝖵}}}$.

D-5.10.7 BFV’s Bootstrapping

BFV’s original bootstrapping procedure (Summary D-2.11.7 in §D-2.11.7) is as follows: (1) modulus switch from $q\to p^{𝜀}$; (2) homomorphic decryption; (3) CoeffToSlot; (4) EvalExp; (5) SlotToCoeff; and (6) re-interpretation.

However, in RNS, we cannot mod-switch to $p^{𝜀}$ because RNS’s base moduli have to be co-prime to each other, whereas the factors of $p^{𝜀}$ are not. To avoid this issue, RNS-based BFV’s bootstrapping instead performs the following: (1) ModRaise_RNS from $q\to \mathit{𝑞𝑏}{b}_{\alpha }$, where $b{b}_{\alpha }$ is an auxiliary base; (2) coefficient multiplication by $p^{𝜀}$; (3) ModSwitch_RNS from $\mathit{𝑞𝑏}{b}_{\alpha }\to b{b}_{\alpha }$; (4) FastBConvEx from $b{b}_{\alpha }\to q$; (5) homomorphic decryption to adjust the scaling factor of the plaintext; (6) CoeffToSlot; (7) EvalExp; (8) SlotToCoeff; and (9) re-interpretation. The detailed procedure is described as follows:

Input: The input BFV ciphertext to bootstrap is $(A,B)modq$, which would decrypt to:

$A\cdot S+B=\mathrm{\Delta }M+E+\mathit{𝐾𝑞}$ # where $\mathrm{\Delta }={\displaystyle \frac{q}{p^r}}$

1.

ModRaise_RNS from $q\to \mathit{𝑞𝑏}{b}_{\alpha }$:

Mod-raise ciphertext $(A,B)modq$ to $(A,B)mod\mathit{𝑞𝑏}{b}_{\alpha }$, which would decrypt to:

$A\cdot S+B=\mathrm{\Delta }M+E+\mathit{𝐾𝑞}+\mathit{𝑈𝑞}(\mathit{𝑚𝑜𝑑}\mathit{𝑞𝑏}{b}_{\alpha })$

# where $\mathit{𝑈𝑞}$ is the FastBConv + SmallMont error, and $U$’s coefficients are either $\{-1,0,1\}$

$$

2.

Coefficient Multiplication by $p^{𝜀}$:

Multiply the coefficients of $(A,B)modq$ by $p^{𝜀}$ to update the ciphertext to $(p^{𝜀}A,p^{𝜀}B)mod\mathit{𝑝𝑏}{b}_{\alpha }$, which would decrypt to:

$p^{𝜀}A\cdot S+p^{𝜀}B=\mathrm{\Delta }{p}^{𝜀}M+p^{𝜀}E+p^{𝜀}\mathit{𝐾𝑞}+p^{𝜀}\mathit{𝑈𝑞}(\mathit{𝑚𝑜𝑑}\mathit{𝑞𝑏}{b}_{\alpha })$

$$

3.

ModSwitch_RNS from $\mathit{𝑞𝑏}{b}_{\alpha }\to b{b}_{\alpha }$:

Mod-switch the ciphertext $(p^{𝜀}A,p^{𝜀}B)mod\mathit{𝑝𝑏}{b}_{\alpha }$ to $\left(\lceil {\displaystyle \frac{p^{𝜀}A}{q}}\rfloor ,\lceil {\displaystyle \frac{p^{𝜀}B}{q}}\rfloor \right)(\mathit{𝑚𝑜𝑑}b{b}_{\alpha })$, which would decrypt to:

$\lceil {\displaystyle \frac{p^{𝜀}A}{q}}\rfloor \cdot S+\lceil {\displaystyle \frac{p^{𝜀}B}{q}}\rfloor ={\displaystyle \frac{\mathrm{\Delta }{p}^{𝜀}M}{q}}+{\displaystyle \frac{p^{𝜀}E}{q}}+{\displaystyle \frac{p^{𝜀}\mathit{𝐾𝑞}}{q}}+{\displaystyle \frac{p^{𝜀}\mathit{𝑈𝑞}}{q}}+𝜖(\mathit{𝑚𝑜𝑑}b{b}_{\alpha })$

# $𝜖$ is a small rounding error

$=p^{𝜀-r}M+{\displaystyle \frac{p^{𝜀}E}{q}}+p^{𝜀}K+p^{𝜀}U+𝜖(\mathit{𝑚𝑜𝑑}b{b}_{\alpha })$

$$

4.

FastBConvEx from $b{b}_{\alpha }\to q$:

Exact fast base conversion of $(p^{𝜀}A,p^{𝜀}B)modb{b}_{\alpha }$ to $(p^{𝜀}A,p^{𝜀}B)modq$, which would decrypt to:

$p^{𝜀-r}M+{\displaystyle \frac{p^{𝜀}E}{q}}+p^{𝜀}K+p^{𝜀}U+𝜖modq$

$$

5.

Homomorphic Decryption:

Now, we have the ciphertext $(p^{𝜀}A,p^{𝜀}B)modq={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }\left(p^{𝜀-r}M+{\displaystyle \frac{p^{𝜀}E}{q}}+p^{𝜀}K+p^{𝜀}U+𝜖\right)modq$. We do homomorphic decryption by using the encrypted private key ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{\mathrm{\Delta }}S)$, where $\widehat{\mathrm{\Delta }}=\lfloor {\displaystyle \frac{q}{p^{𝜀}}}\rfloor$. The output is ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{\mathrm{\Delta }}\cdot (p^{𝜀-r}M+{\displaystyle \frac{p^{𝜀}E}{q}}+p^{𝜀}K+p^{𝜀}U+𝜖))modq$.

$$

6.

Perform CoeffToSlot, digit extraction, and SlotToCoeff. These operations can be performed by only regular RNS-based additions and multiplications. The final digit-extracted ciphertext is ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{\mathrm{\Delta }}\cdot (p^{𝜀-r}\cdot M+K{p}^{𝜀}+U{p}^{𝜀}))$, where all noise values smaller than the (base-$p$) $(𝜀-r)$-th digits are eliminated.

$$

7.

Scaling Factor Re-interpretation:

Theoretically re-interpret the ciphertext without any additional mathematical computation. The ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{\mathrm{\Delta }}\cdot (p^{𝜀-r}\cdot M+K{p}^{𝜀}+U{p}^{𝜀}))$ is mathematically the same as:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{\mathrm{\Delta }}\cdot (p^{𝜀-r}\cdot M+K{p}^{𝜀}+U{p}^{𝜀}))$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M+(K+U)\cdot q)$ # since $\mathrm{\Delta }={\displaystyle \frac{q}{p^r}}$, and $\widehat{\mathrm{\Delta }}={\displaystyle \frac{a}{p^{𝜀}}}$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)modq$.

D-5.10.8 CKKS’s Bootstrapping

CKKS’s original bootstrapping procedure (Summary D-3.13.7 in §D-3.13.7) is as follows: (1) Modraise; (2) homomorphic decryption; (3) CoeffToSlot; (4) EvalExp; (5) CoeffToSlot; (6) Re-interpretation. In the RNS-based CKKS bootstrapping, we perform ModRaise_RNS at step 1, and all other steps are computed by using regular RNS-based addition and multiplication operations. Step 1’s ModRaise_RNS operation generates a $u\cdot q_0$ noise (where $u\in \{-1,0,1\}$ using SmallMont) for each polynomial coefficient during FastBConv. Therefore, step 2’s homomorphic decryption outputs $\mathrm{\Delta }M+E+W\cdot q_0+K\cdot q_0$, where $W\cdot q_0$ represents the aggregation of all coefficient noise terms which are multiplied with the $q_0$-overflow noises generated by FastBConv and SmallMont. The $W\cdot q_0+K\cdot q_0$ term gets eliminated by step 4’s EvalExp which performs approximated modulo reduction based on a sine-graph evaluation whose period is $q_0$.

D-5.10.9 BGV’s Bootstrapping

BGV’s original bootstrapping procedure (§D-4.11) is as follows: (1) modulus switch from $q_l\to \widehat{q}$; (2) ciphertext coefficient multiplication by $p^{𝜀-1}$; (3) ModRaise; (4) CoeffToSlot; (5) EvalExp; (6) homomorphic multiplication by $|p^{-(𝜀-1)}{|}_{p^{𝜀}}$; (7) SlottToCoeff; (8) noise term re-interpretation. Given this procedure, the RNS-based bootstrapping steps are as follows:

Suppose the target BGV ciphertext to bootstrap is $(A,B)mod{q}_l$, where the plaintext modulus (i.e., noise scaling factor) is $p$.

1.

${\mathsf{\text{𝖬𝗈𝖽𝖲𝗐𝗂𝗍𝖼𝗁}}}_{\mathsf{\text{𝖱𝖭𝖲}}}^{\mathsf{\text{𝖡𝖦𝖵}}}$ from $q_l\to \widehat{q}$ where $\widehat{q}$ is a special modulus satisfying the following requirements: $\widehat{q}\equiv 1mod{p}^{𝜀}$, $\widehat{q}\equiv 1modp$, $\widehat{q}$ and $q_l$ are co-prime, and $\widehat{q}<q_l$.

$$

2.

Constant multiplication by $p^{𝜀-1}$ to the coefficients of the ciphertext polynomials $(\widehat{A},\widehat{B})$, which increases the underlying plaintext’s noise scaling factor $\mathrm{\Delta }$ and the plaintext modulus from $p\to p^{𝜀}$. This effectively updates the underlying plaintext to $p^{𝜀-1}M+p^{𝜀}E$.

$$

3.

ModRaise_RNS from $\widehat{q}\to q_L$, which generates an additional noise $|u\cdot \widehat{q}{|}_{q_L}$ (where $u\in \{-1,0,1\}$using SmallMont). At this point, the ciphertext is ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(p^{𝜀-1}M+p^{𝜀}E+\widehat{q}K)mod{q}_L$, whose underlying plaintext is:

$p^{𝜀-1}M+p^{𝜀}E+\widehat{q}K$

$=p^{𝜀-1}M+Kmod{p}^{𝜀}$ # since $\widehat{q}\equiv 1mod{p}^{𝜀}$

After the above steps, the remaining steps (i.e., CoeffToSlot, EvalExp, homomorphic multiplication by $|p^{-(𝜀-1)}{|}_{p^{𝜀}}$, SlotToCoeff, and re-interpretation) can be performed by regular RNS-based addition and multiplication operations.

D-5.10.10 Noise Impact of RNS Operations

When RNS techniques are used in FHE operations, the noise generated by FastBConvEx_RNS, ModRaise_RNS, and ModSwitch_RNS is directly added to each coefficient of the ciphertext polynomials $A$ and $B$. Since the decryption relation is $A\cdot S+B$, even the noise added to the coefficients of the polynomial $A$ gets multiplied by a large factor due to the polynomial multiplication with $S$. Therefore, it is important to always ensure to reduce the generated noise of each FastBConvEx_RNS by using it with SmallMont.

D-5.10.11 Python Source Code of RNS Primitives

We provide a Python script implementing the following exemplary RNS primitives: FastBConv, ModRaise_RNS, ModDrop_RNS, ModSwitch_RNS, SmallMont, and BaseBConvEx.