D-3.13 Modulus Bootstrapping

- Reference: Bootstrapping for Approximate Homomorphic Encryption [18]

During CKKS’s ciphertext-to-ciphertext multiplication, each ciphertext is associated with a particular multiplicative level and it decreases by 1 upon each ciphertext-to-ciphertext multiplication (by its internal modulus rescaling operation). Reaching multiplicative level 0 is equivalent to reaching the end of a ciphertext’s modulus chain and no more ciphertext-to-ciphertext multiplication can be performed. To continue with further ciphertext-to-ciphertext multiplication, CKKS provides a special operation called bootstrapping, which is a process of resetting the ciphertext’s end-of-chain modulus $q_0$ to the initial maximum modulus $q_L$ (which is either $q_0\cdot {\mathrm{\Delta }}^L$ in the vanilla rescaling scheme, or $\underset{m=0}{\overset{L}{\prod <!--\; FUNCTION\; APPLICATION\; -->}}{w}_m$ in the case of using CRT, as explained in §D-3.5.4).

Suppose we have a ciphertext $(A,B)$ with multiplicative depth 0. If we decrypt a ciphertext whose multiplicative level is 0 (i.e., the ciphertext’s modulus is $q_0$), then decrypting it without reduction modulo $q_0$ would output:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}$

$=B+A\cdot S=\mathrm{\Delta }M+E+q_0\cdot K$ # since $B+A\cdot Smod{q}_0=\mathrm{\Delta }M+E$

, where $q_0\cdot K$ accounts for wrap-around modulo $q_0$ values– each coefficient of polynomial $q_{0}K$ is some multiple of $q_0$. CKKS’s bootstrapping procedure is equivalent to safely transforming a ciphertext’s modulus from $q_0$ to $q_L$ (where $q_L\gg q_0$).

D-3.13.1 High-level Idea

As the first step of bootstrapping, we forcibly change the modulus of the ciphertext $(A,B)$ from $q_0$ to $q_L$. Then, its decryption with reduction modulo $q_L$ would output:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}mod{q}_L$

$=B+A\cdot Smod{q}_L$

$=\mathrm{\Delta }M+E+q_{0}Kmod{q}_L$

Here, we assume that $q_L$ is large enough such that $\mathrm{\Delta }M+E+q_{0}K\ll q_L$. This is true given $S$ has small coefficients which are either $\{-1,0,1\}$, and thus the coefficients of $B+A\cdot S$ would not grow much.

In the $\mathrm{\Delta }M+E+q_{0}Kmod{q}_L$ term, notice that because of the $q_{0}K$ term which is not modulo-reduced by $q_0$ anymore, the ciphertext’s decrypted plaintext polynomial’s each $i$-th term would get a corrupted coefficient $\mathrm{\Delta }{m}_i+e_i+q_0\cdot k_{i}mod{q}_L$ instead of $\mathrm{\Delta }{m}_i+e_{i}mod{q}_L$. So, we now need to eliminate the garbage term $q_0\cdot k_{i}mod{q}_L$ in each coefficient and distill the pure plaintext coefficient $\mathrm{\Delta }{m}_i+e_i$.

To do so, we will take an approximated approach by using a sine function described in Figure 16, which has a period of $q_0$ with the amplitude ${\displaystyle \frac{q_0}{2\pi }}$. This sine function has the following two useful properties:

1.

When $f(x)$ is evaluated at $x$ values near the multiple of $q_0$, the result approximates to that of a line function $y=x$. This is because the derivative (slope) of $\sin <!--\; FUNCTION\; APPLICATION\; -->x$ is $y^{\prime }=\cos <!--\; FUNCTION\; APPLICATION\; -->x$, and if $x$ is a multiple of $2\pi$, the slope is: $y^{\prime }=\cos <!--\; FUNCTION\; APPLICATION\; -->2\pi =1$.

2.

The evaluation of $f(x)$ eliminates the multiples of $q_0$ from the input (i.e., modulo reduction $q_0$)

Combining these two properties, given input $x=\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$,

$f(\mathrm{\Delta }{m}_i+e_i+q_0{k}_i)={\displaystyle \frac{q_0}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\pi \cdot (\mathrm{\Delta }{m}_i+e_i+q_0{k}_i))}{q_0}}\right)={\displaystyle \frac{q_0}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\pi \cdot (\mathrm{\Delta }{m}_i+e_i))}{q_0}}\right)\approx \mathrm{\Delta }{m}_i+e_i$

, provided $\mathrm{\Delta }{m}_i+e_i$ is very close to 0 relative to $q_0$ (i.e., $\mathrm{\Delta }{m}_i+e_i\ll q_0$). This is true, because by construction of the CKKS scheme, the plaintext modulus (even with scaling it up by $\mathrm{\Delta }$), is significantly smaller than the ciphertext modulus. Therefore, to remove $q_{0}K$ from $\mathrm{\Delta }M+E+q_{0}K$, we can update each coefficient of the polynomial $\mathrm{\Delta }M+E+q_{0}K$ by evaluating it with the $f(x)$ sine function. However, we cannot directly update the coefficients of the polynomial, because the CKKS scheme (the RLWE scheme in general) only supports the input vector’s slot-wise $\text{(+,⋅)}$ operations. Therefore, to update the polynomial coefficients, we need to express the update logic in terms of slot-wise input vector arithmetic $\text{(+,⋅)}$. Considering all these, CKKS’s overall bootstrapping procedure is described in Table 6.

D-3.13.2 Mathematical Expansion of the High-level Idea

We will mathematically walk through how the bootstrapping procedure (Table 6) correctly updates the modulus of the input ciphertext from $q_0$ to $q_L$.

For ease of understanding, we will first explain how we would do modulus bootstrapping for a ciphertext with multiplicative level 0 (i.e., its modulus is $q_0$) in case we have access to the secret key $S(X)$. Using this key, we can decrypt the ciphertext as follows:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}$ # where $\mathsf{\text{𝖼𝗍}}=(A,B)={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)$

$=B+A\cdot S=\mathrm{\Delta }M+Emod{q}_0$

$=\mathrm{\Delta }M+E+q_{0}K$ # where $q_{0}K$ accounts for any potential wrap-around modulo $q_0$ values

Our initial goal is to bootstrap the modulus of the ciphertext from $q_0$ to $q_L$ by using only the following three tools:

• Secret key $S$
• Batch-encoding (${\sigma }^{-1}$) and decoding ($\sigma$) formulas
• Batched slot-wise $\text{(+,⋅)}$ operation of input vectors based on their batch-encoded polynomials

After explaining the above, we will then explain how to achieve the same bootstrapping without having access to the secret key $S$.

ModRaise: This step forcibly changes the ciphertext’s modulus from $q_0$ to $q_L$ and then decrypts the ciphertext as follows:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}=B+A\cdot S=\mathrm{\Delta }M+E+q_{0}Kmod{q}_L$

Notice that the ciphertext’s decrypted plaintext polynomial’s each $i$-th coefficient gets corrupted to $m_i+e_i+q_0\cdot k_{i}mod{q}_L$. So, we now need to eliminate the garbage term $q_0{k}_{i}mod{q}_L$ in each coefficient and distill the pure plaintext coefficient $\mathrm{\Delta }{m}_i+e_i$.

CoeffToSlot: This step generates a new plaintext polynomial whose each $i$-th input vector slot stores the corrupted coefficient $(m_i+e_i+q_0{k}_i)$. The trick of doing this is to apply CKKS’s batch-encoding mapping ${\sigma }^{-1}$ (which represents the transformation $\overrightarrow{m}={\displaystyle \frac{\tilde{W}\cdot I_n^R\cdot {\overrightarrow{v}}_{{}^{\prime }}}{n}}$ as explained in §D-3.1) to the input vector slots that encode the polynomial $\mathrm{\Delta }M+E+q_{0}Kmod{q}_L$. Let ${\overrightarrow{v}}_c$ be the input vector that corresponds to polynomial $\mathrm{\Delta }M+E+q_{0}K$. Then, ${\overrightarrow{v}}_c$ and $\mathrm{\Delta }M+E+q_{0}K$ satisfy the following relation over the encoding mapping ${\sigma }^{-1}$:

${\sigma }^{-1}({\overrightarrow{v}}_c)=M_c=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(\mathrm{\Delta }{m}_i+e_i+q_0{k}_i)\cdot X^i$ # i.e., polynomial $\mathrm{\Delta }M+E+q_{0}K$

This implies that if we homomorphically apply the ${\sigma }^{-1}$ transformation to the elements of the input vector ${\overrightarrow{v}}_c$, then the resulting input vector ${\overrightarrow{v}}_s$ will store ${\overrightarrow{v}}_c$’s encoded polynomial coefficient values as follows:

${\sigma }^{-1}\circ {\overrightarrow{v}}_c={\overrightarrow{v}}_s=(\mathrm{\Delta }{m}_0+e_0+q_0{k}_0,\mathrm{\Delta }{m}_1+e_1+q_0{k}_1,\cdots ,\mathrm{\Delta }{m}_{n-1}+e_{n-1}+q_0{k}_{n-1})$

# where $\circ$represents a linear transformation operation comprising $\text{(+,⋅)}$

However, remember that at the end of the ModRaise step, we get the decrypted (but corrupted by $q_{0}k$) polynomial $M_c={\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B))=\mathrm{\Delta }M+E+q_{0}K$ and we are not allowed to decode it into ${\overrightarrow{v}}_c$. Therefore, we will instead encode the matrix $\tilde{W}\cdot I_n^R$ in the encoding transformation ${\sigma }^{-1}$ ($\overrightarrow{m}={\displaystyle \frac{\tilde{W}\cdot I_n^R\cdot {\overrightarrow{v}}_{{}^{\prime }}}{n}}$) into its equivalent polynomials (treating a matrix as a combination of vectors) and then perform batched slot-wise $\text{(+,⋅)}$ operation between $M_c$ and the polynomial version of $\tilde{W}\cdot I_n^R$. We express this polynomial-based computation as follows:

$M_s={\sigma }_{{\sigma }^{-1}}^{-1}\circ M_{c}mod{q}_L$ # ${\sigma }_{{\sigma }^{-1}}^{-1}$ is the polynomial-encoded version of the ${\sigma }^{-1}$ transformation

Then, the resulting polynomial $M_s$’s corresponding input vector slots (i.e., the decoded version of $M_s$) will store ${\overrightarrow{v}}_s=(\mathrm{\Delta }{m}_0+e_0+q_0{k}_0,\mathrm{\Delta }{m}_1+e_1+q_0{k}_1,\cdots ,\mathrm{\Delta }{m}_{n-1}+e_{n-1}+q_0{k}_{n-1})$. In other words, the above computation effectively moves the coefficients of $M_c$ to the input vector slots of a new plaintext polynomial.

However, remember that in CKKS, an input vector can store only up to ${\displaystyle \frac{n}{2}}$ slots, whereas we need to store a total of $n$ coefficients of $M_c$ in the input vector slots. Therefore, we technically need to create 2 pieces of $M_s$ as $M_{s1}$ and $M_{s2}$, where the input vector of $M_{s1}$ stores $(\mathrm{\Delta }{m}_0+e_0+q_0{k}_0,\mathrm{\Delta }{m}_1+e_1+q_0{k}_1,\cdots ,\mathrm{\Delta }{m}_{\frac{n}{2}-1}+e_{\frac{n}{2}-1}+q_0{k}_{\frac{n}{2}-1})$, and the input vector of $M_{s2}$ stores $(\mathrm{\Delta }{m}_{\frac{n}{2}}+e_{\frac{n}{2}}+q_0{k}_{\frac{n}{2}},\cdots ,\mathrm{\Delta }{m}_{n-1}+e_{n-1}+q_0{k}_{n-1})$.

EvalExp: Our next step is to update ${\overrightarrow{v}}_s$’s each element $m_i+e_i+q_0{k}_i$ to $m_i+e_i$ by evaluating it with the sine function $f(x)$. Since the output of the CoeffToSlot step is polynomial $M_s$ (technically $M_{s1}$ and $M_{s2}$), we need to apply the evaluation transformation in an encoded form. First, we approximate $f(x)$ as a linear combination comprising only $\text{(+,⋅)}$ operations by using the Taylor series and Euler’s formula (will be explained later). Then, we encode (i.e., $\sigma$) the approximated formula into a polynomial form, and we denote it as ${\sigma }_f$. Finally, we apply the ${\sigma }_f$ transformation to $M_s$ as follows:

${\sigma }_f^{-1}\circ M_{s}mod{q}_L$ # Applying the sine function’s linear transformation to ${\overrightarrow{v}}_s$’s each slot storing $\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$

$=M_t=\sigma ({\overrightarrow{v}}_t)=\sigma ({(\mathrm{\Delta }{m}_i+e_i)}_{i=0}^{n-1})mod{q}_L$

After the linear transformation by the sine function, notice that each $q_0{k}_i$ term gets eliminated from ${\overrightarrow{v}}_s$’s slots (i.e. modulo reduction by $q$) and the resulting vector ${\overrightarrow{v}}_t$ stores only the $\mathrm{\Delta }{m}_i+e_i$ terms.

SlotToCoeff: Now that we have a polynomial $M_t$ whose corresponding input vector ${\overrightarrow{v}}_t$’s slots store garbage-removed coefficients of (i.e., $\mathrm{\Delta }{m}_i+e_i$) our initial plaintext polynomial, our next step is to put these coefficients stored in ${\overrightarrow{v}}_t$ back to the polynomial. This is an exact reverse operation of CoeffToSlot as follows:

${\sigma }_{\sigma }^{-1}\circ M^t=M_b$ # ${\sigma }_{\sigma }^{-1}$ is a polynomial-encoded form of the batch-decoding formula ${\overrightarrow{v}}_{{}^{\prime }}={\tilde{W}}^{\ast }\cdot \overrightarrow{m}$ (§D-3.1)

The result is polynomial $M_b$ whose coefficients are garbage-eliminated (i.e., $q_0{k}_i$-free) versions of $M_c$. Finally, we re-encrypt $M_b$ as ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(M_b)$ as the final modulus-bootstrapped ciphertext.

Bootstrapping Without a Secret Key: So far, we have assumed that we have access to the secret key $S$. With decryption and re-encryption enabled, the above bootstrapping steps described are mathematically equivalent to computing the following:

1.

INPUT: $\mathsf{\text{𝖼𝗍}}=(A,B)mod{q}_0$ # where $\mathsf{\text{𝖼𝗍}}=(A,B)={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M)$

2.

ModRaise: $\mathsf{\text{𝖼𝗍}}=(A,B)mod{q}_L$

3.

Decryption: ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}\mathbf{\text{)}}mod{q}_L$

4.

CoeffToSlot: ${\sigma }_{{\sigma }^{-1}}^{-1}\circ {\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}\mathbf{\text{)}}mod{q}_L$

5.

EvalExp: ${\sigma }_f^{-1}\circ ({\sigma }_{{\sigma }^{-1}}^{-1}\circ {\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}\mathbf{\text{)}})mod{q}_L$

6.

SlotToCoeff: ${\sigma }_{\sigma }^{-1}\circ ({\sigma }_f^{-1}\circ ({\sigma }_{{\sigma }^{-1}}^{-1}\circ {\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}\mathbf{\text{)}}))mod{q}_L$

7.

Re-encryption: ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }({\sigma }_{\sigma }^{-1}\circ ({\sigma }_f^{-1}\circ ({\sigma }_{{\sigma }^{-1}}^{-1}\circ {\mathsf{\text{𝖱𝖫𝖶𝖤}}}^{-1}\mathbf{\text{(}}\mathsf{\text{𝖼𝗍}}=(A,B)\mathbf{\text{)}}\mathbf{\text{)}})))mod{q}_L$

However, the ultimate goal of CKKS bootstrapping is to reset the modulus of a ciphertext from $q_0$ to $q_L$ without having access to $S$.

Meanwhile, one important insight is that CKKS’s ModRaise procedure on the ciphertext $(A,B)mod{q}_0$ from $q_0\to q_L$ effectively transforms the ciphertext into a new one which is an encryption of $\mathrm{\Delta }M+q_{0}K$. Before ModRaise, ciphertext $(A,B)mod{q}_0$’s decryption relation is as follows:

$A\cdot A+B=\mathrm{\Delta }M+E+K{q}_{0}mod{q}_0=\mathrm{\Delta }M+E$

After ModRaise to $(A,B)mod{q}_L$, its decryption relation is as follows:

$A\cdot S+B=\mathrm{\Delta }M+E+K{q}_{0}mod{q}_L=\mathrm{\Delta }M+E+K{q}_0$ # because $\mathrm{\Delta }M+E+K{q}_0\ll q_L$

Therefore, the mod-raised ciphertext $(A,B)mod{q}_L={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathrm{\Delta }M+K{q}_0)$ with noise $E$. Thus, CKKS’s homomorphic bootstrapping strategy is to run the subsequent CoeffToSlot, EvalExp, and SlotToCoeff steps homomorphically based on the ciphertext $(A,B)mod{q}_L$. Running these 3 steps consumes a few multiplicative levels due to the ciphertext-to-ciphertext multiplication operations when homomorphically multiplying the coefficient-to-slot and slot-to-coefficient transformation matrices and homomorphically computing powers of $X$ (i.e., $X^k$) during sine approximation. Therefore, upon completion of these 3 steps, the ciphertext modulus reduces from $q_L\to q_l$ (where $l$ is some integer such that $l<L$).

Note that the result of homomorphic bootstrapping is equal to the explicit bootstrapping based on decryption & re-encryption (if we ignore the small differences in the final ciphertext modulus and the noise). In the following subsections, we will explain the algebraic details of CoeffToSlot, EvalExp and SlotToCoeff steps.

D-3.13.3 Details: CoeffToSlot

Homomorphically moving the coefficients of $M_c$ (i.e., $\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$ for $0\le i\le n-1$) to a new ciphertext’s input vector slots is mathematically equivalent to homomorphically computing ${\sigma }_{{\sigma }^{-1}}^{-1}\circ ({\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathsf{\text{𝖼𝗍}}=(A,B))$, which is equivalent to applying the encoding formula to the input vector slot values of ${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathsf{\text{𝖼𝗍}}=(A,B))$.

As explained in Summary D-3.9 (in §D-3.9), the encoding formula for converting an input vector into a list of polynomial coefficients is $\overrightarrow{m}={\displaystyle \frac{\tilde{W}\cdot I_n^R\cdot {\overrightarrow{v}}_{{}^{\prime }}}{n}}$, where $\tilde{W}$ is a basis of the $n$-dimensional vector space crafted as follows:

$\tilde{W}=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \end{array}\right]$

# where the rotation helper function $J(h)=5^{h}mod2n$

Therefore, given the input ciphertext ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝖼}}}={\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }(\mathsf{\text{𝖼𝗍}}=(A,B))mod{q}_L$ whose plaintext polynomial $M_c$ contains corrupted coefficients, computing ${\sigma }_{{\sigma }^{-1}}^{-1}\circ {\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝖼}}}$ is equivalent to computing . However, one problem here is that each CKKS ciphertext encodes only ${\displaystyle \frac{n}{2}}$ input vector slots, whereas our goal is to move $n$ (corrupted) coefficients of the plaintext polynomial $M_c$ encrypted in . Therefore, we will instead generate 2 ciphertexts, ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝗌1}}}$ and ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝗌2}}}$, such that each ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝗌1}}}$’s input vector slots store ${(\mathrm{\Delta }{m}_i+e_i+q_0{k}_i)}_{0\le i<\frac{n}{2}}$ and ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝗌2}}}$’s input vector slots store ${(\mathrm{\Delta }{m}_i+e_i+q_0{k}_i)}_{\frac{n}{2}\le i<n}$.

We split the $n\times n$ matrix $\tilde{W}\cdot I_n^R$ into four ${\displaystyle \frac{n}{2}}\times {\displaystyle \frac{n}{2}}$ matrices as follows:

• ${[\tilde{W}{I}_n^R]}_{11}$: a matrix comprising the upper left-half section of $\tilde{W}\cdot I_n^R$
• ${[\tilde{W}{I}_n^R]}_{12}$: a matrix comprising the upper right-half section of $\tilde{W}\cdot I_n^R$
• ${[\tilde{W}{I}_n^R]}_{21}$: a matrix comprising the lower left-half section of $\tilde{W}\cdot I_n^R$
• ${[\tilde{W}{I}_n^R]}_{22}$: a matrix comprising the lower right-half section of $\tilde{W}\cdot I_n^R$

Then, we can compute ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝗌1}}}$ and ${\mathsf{\text{𝖼𝗍}}}_{\mathsf{\text{𝗌2}}}$ as follows:

Each homomorphic matrix-vector multiplication (e.g., ) can be done in an efficient manner that reduces the number of homomorphic rotations (§D-2.10). can be computed by applying homomorphic conjugation to ct_c (§D-3.11).

D-3.13.4 Details: EvalExp

We will use the sine function $f(x)={\displaystyle \frac{q}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}\right)$ to approximately eliminate $q_0{k}_i$ from $\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$ by computing $f(\mathrm{\Delta }{m}_i+e_i+q_0{k}_i)\approx \mathrm{\Delta }{m}_i+e_i$. This approximation works if $\mathrm{\Delta }{m}_i+e_i$ is very close to $x=0$ relative to $q_0$ (i.e., $\mathrm{\Delta }{m}_i+e_i\ll q_0$). Still, the elimination of $q_0{k}_i$ is approximate (i.e., $\approx \mathrm{\Delta }{m}_i+e_i$), because $f(x)$ is $y\approx x$ nearby $x=0$, not exactly $y=x$.

One issue is that we need to evaluate $f(x)$ homomorphically based on ct_s1 and ct_s2 as inputs (i.e., and ), but FHE supports only $\text{(+,⋅)}$ operations, whereas the sine graph cannot be formulated by only $\text{(+,⋅)}$. Therefore, we will approximate the sine function $f(x)$ by using the Taylor series (§A-14):

$f(x)=f(a)+{\displaystyle \frac{f^{\prime }(a)}{1!}}(x-a)+{\displaystyle \frac{f^{″}(a)}{2!}}{(x-a)}^2+{\displaystyle \frac{f^{‴}(a)}{3!}}{(x-a)}^3+\cdots =\underset{d=0}{\overset{\infty }{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\displaystyle \frac{f^{(d)}(a)}{d!}}{(x-a)}^d$

If we approximate $f(x)$ around $x=0$, then the approximated polynomial is as follows:

$f(x)={\displaystyle \frac{q_0}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\pi }{q_0}}\cdot 0\right)+{\displaystyle \frac{q_0}{2\pi }}\cdot {\displaystyle \frac{2\pi }{q_0}}\cdot {\displaystyle \frac{\cos <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\pi }{q_0}}\cdot 0\right)}{1!}}\cdot x+{\displaystyle \frac{q_0}{2\pi }}\cdot {\left({\displaystyle \frac{2\pi }{q_0}}\right)}^2\cdot {\displaystyle \frac{-\sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\pi }{q_0}}\cdot 0\right)}{2!}}\cdot x^2+\cdots$

$={\displaystyle \frac{q_0}{2\pi }}\cdot \underset{j=0}{\overset{\infty }{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left({\displaystyle \frac{{(-1)}^j}{(2j+1)!}}\cdot {\left({\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}\right)}^{2j+1}\right)$

$\approx {\displaystyle \frac{q_0}{2\pi }}\cdot \underset{j=0}{\overset{h}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}\left({\displaystyle \frac{{(-1)}^j}{(2j+1)!}}\cdot {\left({\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}\right)}^{2j+1}\right)=\widehat{f}(x)$

, where $\widehat{f}(x)$ is a $(2h+1)$-degree polynomial.

Remember that in the RLWE cryptosystem, $B+\mathit{𝐴𝑆}mod{q}_0=\mathrm{\Delta }M+E$, or $B+\mathit{𝐴𝑆}=\mathrm{\Delta }M+E+q_{0}K$ with some polynomial $K$ representing the wrapping around values of modulo $q_0$. Since the secret key $S$ is an $(n-1)$-degree polynomial whose coefficients are small (i.e., $s_i\in \{-1,0,1\}$), the coefficients of $K$ will have some reasonably small upper bound, which decreases with the sparsity of $S$ (i.e., the frequency of 0 coefficients in $S$). Therefore, the degree of our approximated $\widehat{f}(x)$ only needs to be high enough to accurately evaluate $y$ values between $-q_0\cdot {𝑘}_{\mathit{𝑚𝑎𝑥}}\le x\le q_0\cdot {𝑘}_{\mathit{𝑚𝑎𝑥}}$. The required minimum degree of our approximated Taylor polynomial $\widehat{f}(x)$ increases with $q_0{𝑘}_{\mathit{𝑚𝑎𝑥}}$ (i.e., the upper bound of $x$). Our one issue is that the computation overhead for homomorphic evaluation of a polynomial generally increases exponentially with the degree of the polynomial, which will slow down bootstrapping. To reduce this computation cost, we will leverage Euler’s formula (§A-11) and its square arithmetic:

By substituting $𝜃={\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}$, we will use Euler’s formula. We will also approximate $e^{\mathit{𝑖𝜃}}$ with the Taylor series, but instead of directly approximating $e^{\mathit{𝑖𝜃}}$, we will first approximate $e^{\frac{\mathit{𝑖𝜃}}{2^r}}$ for some large $2^r$. After that, we will iteratively square $e^{\frac{\mathit{𝑖𝜃}}{2^r}}$ a total $r$ times. Then, we get an approximation of ${(e^{\frac{\mathit{𝑖𝜃}}{2^r}})}^{2^r}=e^{\mathit{𝑖𝜃}}$. The reason why we start with the approximation of $e^{\frac{\mathit{𝑖𝜃}}{2^r}}$ instead of $e^{\mathit{𝑖𝜃}}$ is that its approximation requires a small degree of polynomial, as ${\displaystyle \frac{𝜃}{2^r}}$ (i.e., the input to the complex exponential function) is small provided $2^r$ is sufficiently large. Specifically, we learned that $x$ ($=\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$) is upper-bounded by $q_0{𝑘}_{\mathit{𝑚𝑎𝑥}}$, thus $𝜃={\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}$ is upper-bounded by ${\displaystyle \frac{2\pi {𝑘}_{\mathit{𝑚𝑎𝑥}}}{2^r}}$. As the targeted range of $x$ for approximation in $f(x)$ is small, we need a small degree of Taylor series polynomial.

Using the Taylor series with degree $d_0$ around $x=0$, we can approximate $e^{\frac{2\mathit{𝜋𝑖𝑥}}{2^r{q}_0}}$ as:

$f_e(x)=e^{\frac{2\mathit{𝜋𝑖𝑥}}{2^r{q}_0}}\approx \underset{d=0}{\overset{d_0}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\displaystyle \frac{1}{d!}}{\left({\displaystyle \frac{2\mathit{𝜋𝑖𝑥}}{2^r{q}_0}}\right)}^d={\widehat{f}}_e(x)$

Then, we iteratively square ${\widehat{f}}_e$ total $r$ times to get:

${({\widehat{f}}_e(x))}^{2^r}\approx {(f_e(x))}^{2^r}=e^{i\frac{2\mathit{𝜋𝑥}}{q_0}}=e^{\mathit{𝑖𝜃}}$

Then, based on Euler’s formula $e^{i\cdot 𝜃}=\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+i\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->𝜃$, we can derive the following relations:

$\overline{e^{i\cdot 𝜃}}=\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+\overline{i\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->𝜃}$

$e^{-i\cdot 𝜃}=\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃-i\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->𝜃$

$e^{i\cdot 𝜃}-e^{-i\cdot 𝜃}=(\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃+i\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->𝜃)-(\cos <!--\; FUNCTION\; APPLICATION\; -->𝜃-i\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->𝜃)=2i\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃$

$\sin <!--\; FUNCTION\; APPLICATION\; -->𝜃={\displaystyle \frac{-i}{2}}\cdot (e^{i\cdot 𝜃}-e^{-i\cdot 𝜃})$

${\displaystyle \frac{q_0}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->𝜃={\displaystyle \frac{q_0}{2\pi }}\cdot {\displaystyle \frac{-i}{2}}\cdot (e^{i\cdot 𝜃}-e^{-i\cdot 𝜃})$

Substituting $𝜃={\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}$, we finally get:

${\displaystyle \frac{q_0}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}\right)={\displaystyle \frac{q_0}{2\pi }}\cdot {\displaystyle \frac{-i}{2}}\cdot (e^{i\cdot \frac{2\mathit{𝜋𝑥}}{q_0}}-e^{-i\cdot \frac{2\mathit{𝜋𝑥}}{q_0}})$

Using the final relation above, the EvalExp step homomorphically evaluates the approximation of ${\displaystyle \frac{q_0}{2\pi }}\cdot \sin <!--\; FUNCTION\; APPLICATION\; -->\left({\displaystyle \frac{2\mathit{𝜋𝑥}}{q_0}}\right)$ where $x=\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$ as follows:

1.

Homomorphically approximately compute $\widehat{f}(x)=e^{i\cdot \frac{2\mathit{𝜋𝑥}}{q_0}}$.

2.

Homomorphically approximately compute $\overline{\widehat{f}(x)}=e^{-i\cdot \frac{2\mathit{𝜋𝑥}}{q_0}}$ by applying homomorphic conjugation. (§D-3.11) to $\widehat{f}(x)$

3.

Homomorphically compute $\widehat{f}(x)-\overline{\widehat{f}(x)}=e^{i\cdot \frac{2\mathit{𝜋𝑥}}{q_0}}-e^{-i\cdot \frac{2\mathit{𝜋𝑥}}{q_0}}$, and then multiply the result by ${\displaystyle \frac{-i}{2}}$ encoded as CKKS plaintext.

The result of EvalExp is two ciphertexts whose input vector slots store the bootstrapped coefficients of $M_c$, which are modulo-reduced $q_0$ from $\mathrm{\Delta }{m}_i+e_i+q_0{k}_i$ to $\mathrm{\Delta }{m}_i+e_i+e_{\mathit{𝑏𝑖}}$. Note that $e_{\mathit{𝑏𝑖}}$ is a bootstrapping error introduced by the following three factors: (1) the intrinsic homomorphic $\text{(+,⋅)}$ computation noises of the CoeffToSlot, EvalExp, and SlotToCoeff steps; (2) the EvalExp step’s Taylor polynomial approximation error of the exponential function $e^{\mathit{𝑖𝜃}}$; (3) the EvalExp step’s sine graph error, since the graph is not exactly $y=x$ around $x=0$, but only $y\approx x$.

Note that since the output of the CoeffToSlot step was split into 2 ciphertexts (ct_s1 and ct_s2), the output of the EvalExp step is also in 2 ciphertexts: (ct_b1 and ct_b2). The input vector slots of ct_b1 store ${(\mathrm{\Delta }{m}_i+e_i+e_{\mathit{𝑏𝑖}})}_{i=0}^{\frac{n}{2}-1}$, whereas the input vector slots of ct_b2 store ${(\mathrm{\Delta }{m}_i+e_i+e_{\mathit{𝑏𝑖}})}_{i=\frac{n}{2}}^{n-1}$.

D-3.13.5 Details: SlotToCoeff

This step is an exact inverse of the CoeffToSlot step, which is moving the bootstrapped (i.e. modulo-reduced $q_0$) coefficients of $M_v$ stored in the input vector slots back to the final plaintext polynomial $M_f$. Remember that the decoding formula from a polynomial to an input vector (§D-3.1) is ${\overrightarrow{v}}_{{}^{\prime }}={\tilde{W}}^{\ast }\cdot \overrightarrow{m}$, where:

${\tilde{W}}^{\ast }=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(1)})\hfill & \hfill {({\omega }^{J(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(2)})\hfill & \hfill {({\omega }^{J(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(1)})\hfill & \hfill {({\omega }^{J_{\ast }(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \end{array}\right]$

We denote ${[{\tilde{W}}^{\ast }]}_{11}$, ${[{\tilde{W}}^{\ast }]}_{12}$, ${[{\tilde{W}}^{\ast }]}_{21}$, and ${[{\tilde{W}}^{\ast }]}_{22}$ as ${\displaystyle \frac{n}{2}}\times {\displaystyle \frac{n}{2}}$ matrices corresponding to the upper-left, upper-right, lower-left, and lower-right sections of ${\tilde{W}}^{\ast }$. Then, homomorphically applying the decoding formula results in the final bootstrapped ciphertext ct_final modulo $q_L$ whose plaintext polynomial is garbage-eliminated from $\mathrm{\Delta }M+E+q_{0}Kmod{q}_L$ to $\mathrm{\Delta }M+E+E_{b}mod{q}_l$ (where $E_b$ is the bootstrapping error polynomial). Note that the ciphertext modulus changed from $q_L\to q_l$ because we consumed some multiplicative levels for computing ciphertext-to-ciphertext multiplications during polynomial evaluation (i.e., $X^k$). We can derive ct_final by homomorphically applying the decoding transformation ${\tilde{W}}_T$ to the results of the EvalExp step (ct_b1 and ct_b2) as follows:

Note that we do not use ${[{\tilde{W}}^{\ast }]}_{21}$ and ${[{\tilde{W}}^{\ast }]}_{22}$, because we only need to derive the ${\displaystyle \frac{n}{2}}$ input vector slots whose decoding would result in the $n$ coefficients ${(\mathrm{\Delta }{m}_i+e_i+e_{\mathit{𝑏𝑖}})}_{i=0}^{n-1}$ of the final $(n-1)$-degree polynomial. Once we generate a new ciphertext ct_final whose ${\displaystyle \frac{n}{2}}$ input vector slots store ${(\mathrm{\Delta }{m}_i+e_i+e_{\mathit{𝑏𝑖}})}_{i=0}^{n-1}$, then its latter ${\displaystyle \frac{n}{2}}$ conjugate slots get automatically filled with the conjugates of the first ${\displaystyle \frac{n}{2}}$ slot values.

D-3.13.6 Reducing the Bootstrapping Overhead by Sparsely Packing Ciphertext

In many cases, the application of CKKS may use only a small number of input vector slots (e.g., ${\displaystyle \frac{n^{\prime }}{2}}$) out of ${\displaystyle \frac{n}{2}}$ slots. Suppose that such $n^{\prime }$ is some number that divides $n$. Then, we can do a series of homomorphic rotations and multiplications to make the input vector slots store ${\displaystyle \frac{n}{n^{\prime }}}$ repetitions of the ${\displaystyle \frac{n^{\prime }}{2}}$-slot values. Specifically, we can do this in total ${\displaystyle \frac{n}{n^{\prime }}}$ rounds of rotations and additions: initially, we zero-mask between the $\frac{n^{\prime }}{2}$-th slot and the $\frac{n}{2}-1$-th slots and save as ct, and then in each $i$-th round we compute $\mathsf{\text{𝖼𝗍}}=\mathsf{\text{𝖼𝗍}}+\mathsf{\text{𝖱𝗈𝗍𝖺𝗍𝖾}}(\mathsf{\text{𝖼𝗍}},-n^{\prime }\cdot 2^i)$.

Then, we apply the optimization of sparsely packing ciphertext in Summary D-3.12 (§D-3.12): if an ${\displaystyle \frac{n}{2}}$-dimensional input vector is structured as ${\displaystyle \frac{n}{n^{\prime }}}$ consecutive repetitions of the first ${\displaystyle \frac{n^{\prime }}{2}}$ slot values, then its encoded polynomial $M(X)\in \mathbb{Z}[X]∕(X^n+1)$ has the structure such that all its coefficients whose degree term is not a multiple of ${\displaystyle \frac{n}{n^{\prime }}}$ are zero as follows:

$M(X)=c_0+c_{\frac{n}{n^{\prime }}}{X}^{\frac{n}{n^{\prime }}}+c_{\frac{2n}{n^{\prime }}}{X}^{\frac{2n}{n^{\prime }}}+\cdots +c_{n-\frac{n}{n^{\prime }}}{X}^{n-\frac{n}{n^{\prime }}}$.

Remember that in the CoeffToSlot step (§D-3.13.3), we use the formula $\overrightarrow{m}={\displaystyle \frac{\tilde{W}\cdot I_n^R\cdot {\overrightarrow{v}}_{{}^{\prime }}}{n}}$ to move the $q_{0}k$-contaminated polynomial’s coefficients to the input vector slots. But by the principle of sparsely packed ciphertext, we know that all the slots of $\overrightarrow{m}$ which are not a multiple of ${\displaystyle \frac{n}{n^{\prime }}}$ slots would store a zero coefficient. This means that we will get the same computation result even if we only compute the $\overrightarrow{m}={\displaystyle \frac{\tilde{W}\cdot I_n^R\cdot {\overrightarrow{v}}_{{}^{\prime }}}{n}}$ formula with the rows of $\tilde{W}$ whose row index is a multiple of ${\displaystyle \frac{n}{n^{\prime }}}$. Mathematically, we can update the encoding formula to $\overrightarrow{m_s}={\displaystyle \frac{\text{E}\cdot I_{n^{\prime }}^R\cdot {\overrightarrow{v}}_{{}^{\prime }}}{n^{\prime }}}$ where the $n\times \frac{n}{n^{\prime }}$ matrix E is an elimination of all those columns from $\tilde{W}$ whose column index is not a multiple of ${\displaystyle \frac{n}{n^{\prime }}}$: