D-3.5 Homomorphic Ciphertext-to-Ciphertext Multiplication

CKKS’s ciphertext-to-ciphertext multiplication is partially different from that of BFV. In the case of BFV, its ciphertext modulus stays the same after each multiplication. On the other hand, CKKS reduces its ciphertext modulus size by 1 after each multiplication (which is equivalent to reducing its multiplicative level by 1). When the level reaches 0, no more multiplication can be further done (unless we bootstrap the modulus). This difference happens because the two schemes use different strategies in handling their plaintext scaling factors– BFV’s $\mathrm{\Delta }=\lfloor {\displaystyle \frac{q}{t}}\rfloor$, whereas CKKS’s $\mathrm{\Delta }$ can be any value such that $\mathrm{\Delta }\ll q_0$ where $q_0$ is the lowest multiplicative level’s ciphertext modulus. However, both schemes use the similar relinearization technique.

To make it easy to understand, we will explain CKKS’s ciphertext-to-ciphertext multiplication based on this alternate version of RLWE (Theorem B-4.4 in §B-4.4), where the sign of the $\mathit{𝐴𝑆}$ term is flipped in the encryption and decryption formulas.

Suppose we have the following two (CKKS) RLWE ciphertexts:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }{M}^{⟨1⟩})=(A^{⟨1⟩},B^{⟨1⟩})$, where $B^{⟨1⟩}=-A^{⟨1⟩}\cdot S+\mathrm{\Delta }{M}^{⟨1⟩}+E^{⟨1⟩}$

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }{M}^{⟨2⟩})=(A^{⟨2⟩},B^{⟨2⟩})$, where $B^{⟨2⟩}=-A^{⟨2⟩}\cdot S+\mathrm{\Delta }{M}^{⟨2⟩}+E^{⟨2⟩}$

RLWE ciphertext-to-ciphertext multiplication is comprised of the following 2 steps:

1.

Find a formula for the synthetic ciphertext that is equivalent to ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ by leveraging the following congruence relation:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩})\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨2⟩})$

$$

2.

Rescale ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ to ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$.

We will explain each of these steps.

D-3.5.1 Synthetic Ciphertext Derivation

The 1st step of RLWE ciphertext-ciphertext multiplication is to find a way to express the following congruence relation:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩})\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨2⟩})$

in terms of our following known values: $A^{⟨1⟩},B^{⟨1⟩},A^{⟨2⟩},B^{⟨2⟩},S$. First, notice that the following is true:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩}))={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}))\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨2⟩}))$

, because encrypting and decrypting the multiplication of two plaintexts should give the same result as decrypting two encrypted plaintexts and then multiplying them. As the encryption and decryption functions cancel out, we get the following:

${\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩}\approx (\mathrm{\Delta }\cdot M^{⟨1⟩}+E^{⟨1⟩})\cdot (\mathrm{\Delta }\cdot M^{⟨2⟩}+E^{⟨2⟩})$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}))\cdot {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}({\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨2⟩}))$

# where $(\mathrm{\Delta }\cdot M^{⟨1⟩}+E^{⟨1⟩})\cdot (\mathrm{\Delta }\cdot M^{⟨2⟩}+E^{⟨2⟩})={\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩}+\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot E^{⟨2⟩}+\mathrm{\Delta }\cdot M^{⟨2⟩}\cdot E^{⟨1⟩}+E^{⟨1⟩}\cdot E^{⟨2⟩}$, where $E^{⟨1⟩}\cdot E^{⟨2⟩}$ is small enough to be eliminated upon decryption, and $\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot E^{⟨2⟩}$ and $\mathrm{\Delta }\cdot M^{⟨2⟩}\cdot E^{⟨1⟩}$ will be scaled down to $M^{⟨1⟩}\cdot E^{⟨2⟩}$ and $M^{⟨2⟩}\cdot E^{⟨1⟩}$ upon modulus switch later, becoming small enough to be enough to be eliminated during decryption

Remember from §B-4.4 the following:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C=(A,B))=\mathrm{\Delta }M+E=B+A\cdot S$

Thus, the above congruence relation can be rewritten as follows:

${\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩}$ $\approx (\mathrm{\Delta }\cdot M^{⟨1⟩}+E^{⟨1⟩})\cdot (\mathrm{\Delta }\cdot M^{⟨2⟩}+E^{⟨2⟩})$

$=(B^{⟨1⟩}+A^{⟨1⟩}\cdot S-E^{⟨1⟩})\cdot (B^{⟨2⟩}+A^{⟨2⟩}\cdot S-E^{⟨2⟩})$

$\approx (B^{⟨1⟩}+A^{⟨1⟩}\cdot S)\cdot (B^{⟨2⟩}+A^{⟨2⟩}\cdot S)$

$=B^{⟨1⟩}{B}^{⟨2⟩}+(B^{⟨2⟩}{A}^{⟨1⟩}+B^{⟨1⟩}{A}^{⟨2⟩})\cdot S+(A^{⟨1⟩}S)\cdot (A^{⟨2⟩}S)$

$=\underset{D_0}{\underbrace{B^{⟨1⟩}{B}^{⟨2⟩}}}+\underset{D_1}{\underbrace{(B^{⟨2⟩}{A}^{⟨1⟩}+B^{⟨1⟩}{A}^{⟨2⟩})}}\cdot S+\underset{D_2}{\underbrace{(A^{⟨1⟩}\cdot A^{⟨2⟩})}}\cdot \underset{S^2}{\underbrace{(S\cdot S)}}$

$=D_0+D_1\cdot S+D_2\cdot S^2$

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\alpha }=(D_1,D_0))+D_2\cdot S^2$ # since $D_0+D_1\cdot S={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\alpha }=(D_1,D_0))$

In the final step above, we converted $D_0+D_1\cdot S$ into ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\alpha }=(D_1,D_0))$, where $C_{\alpha }$ is the synthetic RLWE ciphertext $(D_1,D_0)$ encrypted by $S$. Similarly, our next task is to derive a synthetic RLWE ciphertext $C_{\beta }$ such that $D_2\cdot S^2={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta })$. The reason why we want this synthetic ciphertext is that we do not want the square of $S$ (i.e., $S^2$), because if we continue to keep $S^2$, then over more consequent ciphertext-to-ciphertext multiplications, this term will aggregate exponentially growing bigger exponents such as $S^4,S^8,\cdots ...$, which would exponentially increase the computational overhead of decryption. In the next subsection, we will explain how to derive the synthetic RLWE ciphertext $C_{\beta }$ such that $D_2\cdot S^2={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta })$.

D-3.5.2 Relinearization Method 1 – Ciphertext Decomposition

As explained in BFV’s ciphertext-to-ciphertext multiplication (§D-2.7.3), relinearization is a process of converting the polynomial triplet $(D_0,D_1,D_2)\in R_{⟨n,q⟩}^3$, which can be decrypted into $\mathrm{\Delta }M$ using $S$ and $S^2$ as keys, into the polynomial pairs $(C_{\alpha },C_{\beta })\in R_{⟨n,q⟩}^2$, which can be decrypted into the same $\mathrm{\Delta }M$ by using $S$ as key. In the previous subsection, we explained that we can convert $D_0$ and $D_1$ into $C_{\alpha }$ simply by viewing $D_0$ and $D_1$ as $C_{\alpha }=(D_1,D_0)$. The process of converting $D_2$ into $C_{\beta }$ is exactly the same as the technique explained in §D-2.7.3, which applies the gadget decomposition (§A-6.4) on $D_2$ and computes an inner product with the RLev encryption (§B-5) of $S^2$. Specifically, we compute the following:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta }=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(D_2),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)⟩)$ # the scaling factors of ${\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)$ are all 1

$=D_{2,1}(E_1^{\prime }+S^2{\displaystyle \frac{q}{\beta }})+D_{2,2}(E_2^{\prime }+S^2{\displaystyle \frac{q}{{\beta }^2}})+\cdots +D_{2,l}(E_l^{\prime }+S^2{\displaystyle \frac{q}{{\beta }^l}})$

$=\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(E_i^{\prime }\cdot D_{2,i})+S^2\cdot (D_{2,1}{\displaystyle \frac{q}{\beta }}+D_{2,2}{\displaystyle \frac{q}{{\beta }^2}}+\cdots +D_{2,l}{\displaystyle \frac{q}{{\beta }^l}})$

$=\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{𝜖}_i+D_2\cdot S^2$ # where ${𝜖}_i=E_i^{\prime }\cdot D_{2,i}$

$\approx D_2\cdot S^2$ # because $\underset{i=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{𝜖}_i\ll D_2\cdot E^{″}$ (where $E^{″}$ is the noise embedded in ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(S^2)$

Finally, we get the following relation:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})\approx C_{\alpha }+C_{\beta }$ , where $C_{\alpha }=(D_1,D_0),C_{\beta }=⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(D_2),{\mathsf{\text{𝖱𝖫𝖾𝗏}}}_{S,\sigma }^{\beta ,l}(S^2)⟩$

In the next subsection, we introduce another (older) relinearization technique.

D-3.5.3 Relinearization Method 2 – Ciphertext Modulus Switch

At the setup stage of the RLWE scheme, we craft a special pair of polynomials modulo $q$ as follows:

$A^{\prime }\underset{}{\overset{\$}{\leftarrow }}{R}_{⟨n,q⟩}^k$

$E^{\prime }\underset{}{\overset{\sigma }{\leftarrow }}{R}_{⟨n,q⟩}$

$\mathrm{𝑒𝑣𝑘}=(A^{\prime },-A^{\prime }\cdot S+E^{\prime }+S^2)\in R_{⟨n,q⟩}^2$

$\mathrm{𝑒𝑣𝑘}$ is called an evaluation key, which is essentially a RLWE ciphertext of $S^2$ encrypted by the secret key $S$ without any scaling factor $\mathrm{\Delta }$. Remember that our goal is to find a synthetic RLWE ciphertext $C_{\beta }$ such that decrypting it gives us $D_2\cdot S^2$, that is: ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta })=D_2\cdot S^2$. Let’s suppose that $C_{\beta }=D_2\cdot \mathrm{𝑒𝑣𝑘}$. Then, decrypting $C_{\beta }$ gives us the following:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta }=(D_2\cdot \mathrm{𝑒𝑣𝑘}))={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C=(D_2{A}^{\prime },-D_2{A}^{\prime }\cdot S+D_2{E}^{\prime }+D_2\cdot S^2))$

$=D_2{A}^{\prime }\cdot S-D_2{A}^{\prime }\cdot S+D_2{E}^{\prime }+D_2\cdot S^2$

$=D_2{E}^{\prime }+D_2\cdot S^2$

But unfortunately, $D_2{E}^{\prime }+D_2\cdot S^2\not\approx D_2\cdot S^2$, because $D_2{E}^{\prime }\not\approx 0$ (as $D_2$ is not necessarily a small number).This is because $D_2=A^{⟨1⟩}\cdot A^{⟨2⟩}$, $D_2{E}^{\prime }$ can be any arbitrary value between $[0,q)$.

To solve the above problem, we modify the evaluation key as a set of polynomials in big modulo $g$ as follows:

$A^{\prime }\underset{}{\overset{\$}{\leftarrow }}{R}_{⟨n,q⟩}^k$

$E^{\prime }\underset{}{\overset{\sigma }{\leftarrow }}{R}_{⟨n,q⟩}$

$g\underset{}{\overset{\$}{\leftarrow }}{\mathbb{Z}}_{q_L^2}$ # where $g$ is some large integer power of 2, $q_L$ is the largest modulo before any relinearization

$\mathrm{𝑒𝑣}{𝑘}_{𝑔}=(A^{\prime },-A^{\prime }\cdot S+E^{\prime }+g{S}^2)\in R_{⟨n,\mathit{𝑔𝑞}⟩}^2$

$\mathrm{𝑒𝑣}{𝑘}_{𝑔}$ is essentially an RLWE ciphertext of $g{S}^2$ encrypted by $S$. We can derive the following:

$\mathrm{𝑒𝑣}{𝑘}_{𝑔}=(A^{\prime },-A^{\prime }\cdot S+E^{\prime }+g{S}^2)\in R_{⟨n,\mathit{𝑔𝑞}⟩}^2$

$=(A^{\prime }\text{ mod }\mathit{𝑔𝑞},-A^{\prime }\cdot S+E^{\prime }+g{S}^2\text{ mod }\mathit{𝑔𝑞})$

$=(A^{\prime }+k_2\mathit{𝑔𝑞},-A^{\prime }\cdot S+E^{\prime }+g{S}^2+k_1\mathit{𝑔𝑞})$ (for some integers $k_1,k_2$)

Note that $D_2=A^{⟨1⟩}\cdot A^{⟨2⟩}\in R_{⟨n,q⟩}$

$=D_2\text{ mod }q$

$=D_2+k_{3}q$ (for some integer $k_3$)

Now, let’s multiply $D_2$ to each component of $\mathrm{𝑒𝑣}{𝑘}_{𝑔}$ as follows:

$(A^{\prime }+k_2\mathit{𝑔𝑞},-A^{\prime }\cdot S+E^{\prime }+g{S}^2+k_1\mathit{𝑔𝑞})\cdot (D_2+k_{3}q)$

$=(D_2{A}^{\prime }+D_2{k}_2\mathit{𝑔𝑞}+k_{3}q{A}^{\prime }+k_{3}q{k}_2\mathit{𝑔𝑞},$

$-D_2{A}^{\prime }\cdot S+D_2{E}^{\prime }+g{D}_2\cdot S^2+D_2{k}_1\mathit{𝑔𝑞}-k_{3}q{A}^{\prime }\cdot S+k_{3}q{E}^{\prime }+k_3\mathit{𝑞𝑔}{S}^2+k_{3}q{k}_1\mathit{𝑔𝑞})$

Now, we switch the modulus of this RLWE ciphertext from $\mathit{𝑔𝑞}\to q$ based on the technique in §C-4.5:

$(\lceil {\displaystyle \frac{D_2{A}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{k}_2\mathit{𝑔𝑞}}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{k}_2\mathit{𝑔𝑞}}{g}}\rfloor ,-\lceil {\displaystyle \frac{D_2{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{g{D}_2\cdot S^2}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{k}_1\mathit{𝑔𝑞}}{g}}\rfloor -\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{k_3\mathit{𝑞𝑔}{S}^2}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{k}_1\mathit{𝑔𝑞}}{g}}\rfloor )$

$=(\lceil {\displaystyle \frac{D_2{A}^{\prime }}{g}}\rfloor +D_2{k}_{2}q+\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }}{g}}\rfloor +k_{3}q{k}_{2}q,$

$-\lceil {\displaystyle \frac{D_2{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor +D_2\cdot S^2+D_2{k}_{1}q-\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor +k_{3}q{S}^2+k_{3}q{k}_{1}q)$

$=(\lceil {\displaystyle \frac{D_2{A}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }}{g}}\rfloor \text{ mod }q,-\lceil {\displaystyle \frac{D_2{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor +D_2\cdot S^2-\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor \text{ mod }q)$

$=C_{\beta }\in R_{n,q}^2$

Now, we finally got $C_{\beta }$ which is in the form of RLWE ciphertext modulo $q$. Remember that our goal is to express $D_2\cdot S^2$ as a decryption of RLWE ciphertext. If we treat $C_{\beta }$ as a synthetic RLWE ciphertext and decrypt it, we get the following:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta })$ # where $C_{\beta }$ is treated as a synthetic RLWE ciphertext

$={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}((-\lceil {\displaystyle \frac{D_2{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor +D_2\cdot S^2-\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor ,\lceil {\displaystyle \frac{D_2{A}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }}{g}}\rfloor ))$

$=-\lceil {\displaystyle \frac{D_2{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor +D_2\cdot S^2-\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{A}^{\prime }}{g}}\rfloor \cdot S+\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }}{g}}\rfloor \cdot S$

$\approx \lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor +D_2\cdot S^2+\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor$ # $-\lceil {\displaystyle \frac{D_2{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{D_2{A}^{\prime }}{g}}\rfloor \cdot S=-\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }\cdot S}{g}}\rfloor +\lceil {\displaystyle \frac{k_{3}q{A}^{\prime }}{g}}\rfloor \cdot S\approx 0$

$\approx D_2\cdot S^2$ # $\lceil {\displaystyle \frac{D_2{E}^{\prime }}{g}}\rfloor \approx 0$, $\lceil {\displaystyle \frac{k_{3}q{E}^{\prime }}{g}}\rfloor \approx 0$

As shown in the above, decrypting $C_{\beta }$ gives us $D_2\cdot S^2$. Therefore, we reach the following conclusion:

${\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩}\approx {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\alpha })+{\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C_{\beta })$ , where $C_{\alpha }=(D_1,D_0),C_{\beta }=\lceil {\displaystyle \frac{D_2\cdot \mathrm{𝑒𝑣}{𝑘}_{𝑔}}{g}}\rfloor$

Therefore, we finally get the following congruence relation:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})\approx C_{\alpha }+C_{\beta }$ , where $C_{\alpha }=(D_1,D_0),C_{\beta }=\lceil {\displaystyle \frac{D_2\cdot \mathrm{𝑒𝑣}{𝑘}_{𝑔}}{g}}\rfloor$

Our last step of ciphertext-to-ciphertext multiplication is to convert ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ into ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$, because if the result of ciphertext-to-ciphertext multiplication is $M^{⟨1⟩}\cdot M^{⟨2⟩}=M^{⟨3⟩}$, then for consistency purposes, the resulting RLWE ciphertext is supposed to be:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨3⟩})$

We will explain this process in the next subsection.

D-3.5.4 Rescaling

To convert ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ into ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$, we cannot simply divide the ciphertext ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ by $\mathrm{\Delta }$, because as explained in §A-1.2.2, modulo arithmetic does not support direct division. Multiplying the RLWE ciphertext by ${\mathrm{\Delta }}^{-1}$ (i.e., an inverse of $\mathrm{\Delta }$) does not work either, because the only useful property we can use for inverse multiplication is: $a\cdot a^{-1}\equiv 1$. If an inverse is multiplied to any other values other than its counterpart, the result is an arbitrary value. For example, if ${\mathrm{\Delta }}^{-1}$ is multiplied to a noise (i.e., ${\mathrm{\Delta }}^{-1}E$), then the result can be a very huge value. Thus, multiplying the RLWE ciphertext by ${\mathrm{\Delta }}^{-1}$ does not help due to the unpredictable result of the noise term.

The safest way to convert ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ into ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$ is modulus switch (§C-4.5), which is essentially modulo rescaling (§A-12). For this to work, the RLWE setup stage should design the ciphertext domain $q$ as $q_0\cdot {\mathrm{\Delta }}^L$, where $L$ is denoted as the level of multiplication, and $q_0\gg \mathrm{\Delta }$ (which is important for the accuracy of homomorphic modulo reduction during bootstrapping in §D-3.13). Upon each ciphertext-to-ciphertext multiplication, we switch the modulus of the RLWE ciphertext from $q_0\cdot {\mathrm{\Delta }}^i\to q_0\cdot {\mathrm{\Delta }}^{i-1}$, which effectively converts the plaintext’s squared scaling factor ${\mathrm{\Delta }}^2$ (in ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\mathrm{\Delta }}^2\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$) into $\mathrm{\Delta }$ (in ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }\cdot M^{⟨1⟩}\cdot M^{⟨2⟩})$). Once the RLWE ciphertext’s level reaches 0 (i.e., ciphertext modulus $q_0$), we cannot do any more ciphertext-to-ciphertext multiplication, in which case we need a special process called bootstrapping to re-initialize the modulus level to $L$.

However, one problem with this setup is that ${\mathrm{\Delta }}^L$ will be a huge number. Performing homomorphic addition or multiplication over modulo ${\mathrm{\Delta }}^L$ is computationally expensive. To reduce the overhead of ciphertext size, we use the Chinese remainder theorem (§A-13): given an integer $x\text{ mod }W$ where $W$ is a multiplication of $L+1$ co-primes such that $W=w_0{w}_1{w}_2{w}_3\cdots w_L$, the following congruence relationships hold:

$x\equiv d_0\text{ mod }{w}_0$

$x\equiv d_1\text{ mod }{w}_1$

$x\equiv d_2\text{ mod }{w}_2$

$⋮$

$x\equiv d_L\text{ mod }{w}_L$

, where $x=\underset{m=0}{\overset{L}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{d}_m{y}_m{z}_m\text{ mod }W,y_m={\displaystyle \frac{W}{w_m}},z_m=y_m^{-1}\text{ mod }{w}_m$, and $w_0=q_0$

In other words, $xmodW$ can be isomorphically mapped to a vector of smaller numbers $(d_0,d_1,\cdots ,d_l)$ each in modulo $w_0,w_1,\cdots ,w_l$, addition/multiplication with big elements in modulo $W$ can be done by using their encoded smaller-magnitude CRT vectors element-wise, and later decode the intended big-number result. By leveraging this property, we design the CKKS scheme’s maximal ciphertext modulus as $W=\underset{m=0}{\overset{L}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}{w}_m$, where $L$ is the maximum multiplicative level, $w_0=q_0\gg \mathrm{\Delta }$, and all other $w_i\approx \mathrm{\Delta }$. Then, whenever reaching from the $l$-th to the next lower $l-1$-th multiplicative level, we switch its modulus from $q=\underset{m=0}{\overset{l}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}{w}_m$ to $\widehat{q}=\underset{m=0}{\overset{l-1}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}{w}_m$ as follows:

$(C=(A,B))\in R_{⟨n,q⟩}\to {\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\widehat{C}=(\widehat{A},\widehat{B}))\in R_{⟨n,\widehat{q}⟩}$

$q=\underset{m=0}{\overset{l}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}{w}_m$, # where all $w_m$ are prime numbers, $w_0=q_0\gg \mathrm{\Delta }\cdot p$ to ensure the scaled plaintext $\mathrm{\Delta }M$ during homomorphic operations never overflows the ciphertext modulus even at the lowest multiplicative level, and all other $w_i\approx \mathrm{\Delta }$

$\widehat{q}={\displaystyle \frac{q}{w_l}}$

$\widehat{A_i}=\lceil {\displaystyle \frac{\widehat{q}}{q}}\cdot A_i\rfloor ={\widehat{a}}_{i,0}+{\widehat{a}}_{i,1}X+{\widehat{a}}_{i,2}{X}^2+\cdots +{\widehat{a}}_{i,n-1}{X}^{n-1}$, where each ${\widehat{a}}_{i,j}=\lceil a_{i,j}{\displaystyle \frac{\widehat{q}}{q}}\rfloor =\lceil {\displaystyle \frac{a_{i,j}}{w_l}}\rfloor \in {\mathbb{Z}}_{\widehat{q}}$

$\widehat{B}=\lceil {\displaystyle \frac{\widehat{q}}{q}}\cdot B\rfloor ={\widehat{b}}_0+{\widehat{b}}_{1}X+{\widehat{b}}_2{X}^2+\cdots +{\widehat{b}}_{n-1}{X}^{n-1}$, where each ${\widehat{b}}_j=\lceil b_j{\displaystyle \frac{\widehat{q}}{q}}\rfloor =\lceil {\displaystyle \frac{b_j}{w_l}}\rfloor \in {\mathbb{Z}}_{\widehat{q}}$

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)=(\widehat{A},\widehat{B})\in R_{⟨n,\widehat{q}⟩}$

The above update of $({\{A_i\}}_{i=0}^{k-1},B)$ to $({\{{\widehat{A}}_i\}}_{i=0}^{k-1},\widehat{B})$ effectively changes $\mathrm{\Delta },E$ to $\widehat{\mathrm{\Delta }},\widehat{E}$ as follows:

$\widehat{E}={\widehat{e}}_0+{\widehat{e}}_{1}X+{\widehat{e}}_2{X}^2+\cdots +{\widehat{e}}_{n-1}{X}^{n-1}$, where each ${\widehat{e}}_j=\lceil e_j{\displaystyle \frac{\widehat{q}}{q}}\rfloor =\lceil {\displaystyle \frac{e_j}{w_l}}\rfloor \in {\mathbb{Z}}_{\widehat{q}}$

$\widehat{\mathrm{\Delta }}=\lceil {\mathrm{\Delta }}^2{\displaystyle \frac{\widehat{q}}{q}}\rfloor =\lceil {\displaystyle \frac{{\mathrm{\Delta }}^2}{w_l}}\rfloor \approx \mathrm{\Delta }$ # If we treat $\widehat{\mathrm{\Delta }}$ as $\mathrm{\Delta }$, the rounding error slightly increases the noise $\widehat{E}$ to $\widehat{E}+E_{\mathrm{\Delta }}$, while the decryption of $(\widehat{A},\widehat{B})$ outputs the same $M$

Note that after the rescaling, the plaintext scaling factor of $(\widehat{A},\widehat{B})$ is also updated to $\widehat{\mathrm{\Delta }}$. Meanwhile, $M$ and $S$ stay the same as before.

After we switch the modulus of the ciphertext $C$ from $q\to \widehat{q}$ by multiplying ${\displaystyle \frac{\widehat{q}}{q}}$ to $A$ and $B$, the encrypted original plaintext term ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}$ will become ${\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}\cdot {\displaystyle \frac{\widehat{q}}{q}}={\displaystyle \frac{{\mathrm{\Delta }}^2{M}^{⟨1⟩}{M}^{⟨2⟩}}{w_l}}=(\mathrm{\Delta }+{𝜖}_{\mathrm{\Delta }})\cdot M^{⟨1⟩}{M}^{⟨2⟩}$, where ${𝜖}_{\mathrm{\Delta }}\approx 0$, because as explained before, we chose ${\{w_i\}}_{i=1}^L$ such that $w_i\approx \mathrm{\Delta }$. Therefore, $(\mathrm{\Delta }+{𝜖}_{\mathrm{\Delta }})\cdot M^{⟨1⟩}{M}^{⟨2⟩}=\mathrm{\Delta }{M}^{⟨1⟩}{M}^{⟨2⟩}+{𝜖}_{\mathrm{\Delta }}{M}^{⟨1⟩}{M}^{⟨2⟩}$, where ${𝜖}_{\mathrm{\Delta }}{M}^{⟨1⟩}{M}^{⟨2⟩}\approx 0$, which becomes part of the noise term of the modulus-switched (i.e., rescaled) new ciphertext $\widehat{C}$.

The benefit of this design of the CRT (Chinese remainder problem)-based ciphertext modulus and rescaling is that we can isomorphically decompose the huge coefficients (bigger than 64 bits) of polynomials in ciphertexts into $l$-dimensional Chinese remainder vectors (Theorem A-13.2 in §A-13) and perform element-wise addition or multiplication for computing coefficients over the small vector elements. This promotes computational efficiency for homomorphic addition and multiplication over a large ciphertext modulus (although the number of addition/multiplication operations increases). This technique is called Residue Number System (RNS). When CRT is used in ciphertexts, the security regarding the ciphertext modulus depends on the smallest and the largest CRT elements.

Initial Scaling Factor $\mathbf{\Delta }$ Upon Encryption: To support multi-level multiplicative levels (using CRT), we need to modify the generic scaling factor setup presented in Summary B-4.2 (§B-4.2) from $\mathrm{\Delta }={\displaystyle \frac{q}{t}}$ to $\mathrm{\Delta }=w_L$.

Noise Growth: Upon each step of rescaling during ciphertext-ciphertext multiplication, the noise also gets scaled down by ${\displaystyle \frac{1}{\mathrm{\Delta }}}$ (or by ${\displaystyle \frac{1}{w_l}}$ at multiplicative level $l$ in the case of using CRT). Therefore, if the accumulated noise is smaller than $\mathrm{\Delta }$ ($w_l$ in the case of using CRT), running a single ciphertext-ciphertext multiplication operation effectively reduces the noise against growing. However, during each ciphertext-to-ciphertext multiplication, the encrypted (noisy) plaintext is $(\mathrm{\Delta }{M}_1+E_1)\cdot (\mathrm{\Delta }{M}_2+E_2)={\mathrm{\Delta }}^2{M}_1{M}_2+\mathrm{\Delta }\cdot (M_1{E}_2+M_2{E}_1)+E_1{E}_2$, and rescaling roughly has the effect of dividing this by $\mathrm{\Delta }$, which approximately gives us $\mathrm{\Delta }{M}_1{M}_2+M_1{E}_2+M_2{E}_1+{\displaystyle \frac{E_1{E}_2}{\mathrm{\Delta }}}$. Because of the $(M_1{E}_2+M_2{E}_1)$ term, the noise actually grows compared to before ciphertext-to-ciphertext multiplication. Therefore, ciphertext-to-ciphertext multiplication inevitably increases the noise.

D-3.5.5 Comparing BFV and CKKS Bootstrapping

CKKS bootstrapping shares several common aspects with BFV bootstrapping. CKKS’s ModRaise and Homomorphic Decryption steps are equivalent to BFV’s Homomorphic Decryption (without modulo-$q$ reduction) step. BFV homomorphically multiplies polynomial $A$ and $B$ whose coefficients are in ${\mathbb{Z}}_{p^e}$ with the encrypted secret key whose ciphertext modulus is $q$, which generates the modulo wrap-around coefficient values $p^{e}K$. Similarly, CKKS coefficients are in ${\mathbb{Z}}_{q_0}$ with the encrypted secret key whose ciphertext modulus is $q_L$, which generates the modulo wrap-around coefficient values $q_{0}K$. However, they use different strategies to handle their modulo wrap-around values. CKKS uses evaluation of the sine function having a period of $q_0$ to approximately eliminate $q_{0}K$ (i.e., EvalExp). On the other hand, BFV uses digit extraction to scale down $p^{e}K$ by $p^{e-1}$ and then treats the remaining small $\mathit{𝑝𝐾}$ as part of the modulo wrap-around value of the plaintext. The requirement of the digit extraction algorithm is that the plaintext inputs should be represented as base-$p$ values, and because of this, BFV bootstrapping includes the initial step of modulus switch from $q\to p^e$, where $p^e$ is used as the plaintext modulus after homomorphic decryption.

Both BFV and CKKS use the same strategy for their CoeffToSlot, SlotToCoeff, and Scaling Factor Re-interpretation steps.

Multiplicative Level: A critical difference between BFV and CKKS is that in BFV, the ciphertext modulus $q$ stays the same after ciphertext-ciphertext multiplication, and there is no restriction on the number of ciphertext-ciphertext multiplications. On the other hand, in CKKS, the ciphertext modulus changes from $q_l\to q_{l-1}$ after each multiplication, and when it reaches $q_0$, no more multiplication can be done, unless we reset the ciphertext modulus to $q_L$ by using the modulus bootstrapping technique (§D-3.13).

Limitation of Noise Handling: Although CKKS’s rescaling during ciphertext-to-ciphertext multiplication reduces the magnitude of noise $E$ by $\mathrm{\Delta }$, it also reduces the ciphertext modulus by the same amount, and thus the relative noise-to-ciphertext-modulus ratio does not get decreased by rescaling. In order to reduce (or reset) the noise-to-modulus ratio, we need to do bootstrapping (§D-3.13), which will be explained at the end of this section.

D-3.5.6 Summary

To put all things together, CKKS’s ciphertext-to-ciphertext multiplication is summarized as follows: