# XV. Bootstrapping

[TOC]

## Introduction
Congratulation！👏👏 This is the last chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. In the [previous chapter](https://hackmd.io/PvqvO0EDQQy2FM95Igx8kg), we introduced the rescaling technique, which resolves the issue of the squared scaling factor $\Delta$. However, each rescaling step removes one modulus $q_i$ from the modulus chain, leaving only a single modulus after repeated operations. As a result, CKKS is inherently a *leveled* homomorphic encryption scheme: a ciphertext can support only a finite computational depth before its noise becomes unsustainable.

Bootstrapping overcomes this limitation. It “refreshes’’ a ciphertext by reducing its noise and restoring its modulus level, thereby enabling computations of unbounded depth by using the approximating the modular reduction function with a **scaled sine function**. Since the message $m$ is small relative to $q$, the decryption function $[t]_q$ is periodic and behaves like $\frac{q}{2\pi}\sin(\frac{2\pi t}{q})$ near the message.

The chapter refers to the original version of bootstrapping, which is quite slow. For the modern bootstrapping algorithms, check the links in Further Reading section.

## **Notations**
- $Q_0=q_0$: The base modulus q_i at leveled 0 (minimum level)
- $Q_l=\prod_{i=0}^l q_i$: The product of moduli chain leveled $l$
- $Q_L = \prod_{i=0}^L q_i$: The product of moduli chain leveled $L$ (maximum level)
- $\mathcal{Q}_l=\{q_0, q_1, ..., q_l\}$: The set of moduli chain level $l$. ($\,l$ can be 0, 1, ..., $L$)
- $\mathcal{R} = \mathbb{Z}[X]/(X^N+1)$: The ring of integers.
- $q_l$: The ciphertext modulus at level $l$.
- $c = (c_0, c_1) \in \mathcal{R}_{q_l}^2$: A ciphertext at level $l$.
- $[t]_q$: Modular reduction of $t$ into the interval $(-q/2, q/2]$.
- $\langle ct, sk \rangle = c_0 + c_1 \cdot s$: The linear decryption structure.
- $\tau: \mathcal{R} \to \mathbb{C}^{N/2}$: The canonical embedding (decoding) map.
- $\Delta\in\mathbb{Z}$: The scaling factor which is approximate to each prime in $\mathcal{Q}_l$
- **$\text{Conv}_{\mathcal{Q}_0 \rightarrow \mathcal{Q}_{L/0}}$**: Fast basis conversion algorithm that converts an RNS representation from basis $\mathcal{Q}_0$ to basis $\mathcal{Q}_{L/0}$.

## **Bootstrapping Algorithm (RNS Perspective)**
The bootstrapping procedure refreshes a ciphertext $c$ with a small modulus $Q_0$ to a new ciphertext $c'$ with a large modulus $Q_L$ (level $L$).

### **Step 1: Modulus Raising (ModUp)**
- Assume the current ciphertext $c \in \mathcal{R}_{q_0}^2$ encrypting the message $m(X)$ and containing error term $I(X)$, such that
$$\langle c, sk \rangle=t(X) =m(X)+I(X)$$
- Transform the ciphertext $c \pmod{q_0}$ into a ciphertext modulo $Q_L$, where $Q_L \gg Q_0$. $(Q_0$ is the first prime in $Q_L)$
$$\text{ModUp}([c]_{\mathcal{Q}_0}) = [c]_{\mathcal{Q}_L}$$
- After modulus raising ($\text{Modup}$), now we have
\begin{align}
t(X) &= q_0\cdot I(X) + m(X) +e_{small}(X)&\pmod{Q_L}\\
&=(m_0+q_0I_0)+\cdots+(m_{N-1}+q_{N-1}I_{N-1})X^{N-1} +e_{small}(X)&\pmod{Q_L} \\
&=t_0+t_1X+\cdots+t_{N-1}X^{N-1}+e_{small}(X) &\pmod{Q_L}
\end{align}
*($e_{small}(X)$ can be ignored, since it is very small compared to $Q_L$)*

### **Step 2: CoeffToSlot (Linear Transformation)**
- At this stage, we have the ciphertext
$$c(X)=a(X)\cdot s(X)+t(X)+e_{small}(X)$$
This ciphertext encrypts $t(X)$ and is equivalent to encrypt the message slot $$z=[t(\zeta_0), t(\zeta_1), \cdots , t(\zeta_{N/2-1})]$$
- Applying homomorphic conjugation, we have a $c_{conj}(X)$ that encrypts
$$\bar z=[\overline{t(\zeta_0)}, \overline{t(\zeta_1)}, \cdots , \overline{t(\zeta_{N/2-1})}]$$
Recall that the Vandermonde Matrix $V$:
$$ V = \begin{pmatrix}
1 & \zeta_0 & \zeta_0^2 & \dots & \zeta_0^{N-1} \\
1 & \zeta_1 & \zeta_1^2 & \dots & \zeta_1^{N-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \zeta_{N/2-1} & \zeta_{N/2-1}^2 & \dots & \zeta_{N/2-1}^{N-1}
\end{pmatrix} $$
- Now if we can see $t(X)$ in plaintext, we have the relationship:
$$z = V \cdot t, \;\text{where}\; \vec t = [t_0, \dots, t_{N/2-1}, t_{N/2}, \dots t_{N-1}]$$
- Thus, we apply homomorphic linear transformation $$t = \frac{1}{N}(\overline{V}^T \cdot z + V^T \cdot \overline{z})$$
The output is a new ciphertext polynomial $ct_{new}$ encrypting $m(X)$ that encodes $[t_0, t_1, \cdots, t_{N-1}]$.This means we have a ciphertext $ct_{new}$ encrypting the coefficients of $t(X)$.
- This step consumes moduli levels. The multiplications utilize the "rescaling" operation. We multiply by a matrix diagonal, then rescale (drop an RNS limb $q_i$) to keep noise manageable.

### **Step 3: EvalExp (Homomorphic Modular Reduction)**
We cannot simply apply modular reduction on the slots, since the plaintext slots are encoded as a polynomial and encrpyted. Thus, we create **Modular Reduction Function** working on the slots. This reduction function required that $m_i\ll q_0$, or the approximation will not be accurate.

#### Modular Reduction Function
- Compute the modular reduction approximately using the complex exponential function. Instead of computing $[t_i]_q$ directly, we compute:
$$E(t) = \frac{q}{2\pi} \exp\left(\frac{2\pi i\cdot t}{q}\right)$$ Since $t = qI + m$ and $I$ is an integer, we have $$\exp(\frac{2\pi i (qI+m)}{q}) = \exp(2\pi i I) \cdot \exp(\frac{2\pi i m}{q}) = \exp(\frac{2\pi i m}{q})$$

#### Algorithm (Double-Angle Formula):
1. **Initial Approximation:** Compute a Taylor polynomial $P_0(t)$ of degree $d_0$ for $\exp(\frac{2\pi i \cdot t}{2^r \cdot q})$.
$$P_0(t) = \Delta \cdot \sum_{k=0}^{d_0} \frac{1}{k!} \left( \frac{2\pi i \cdot t}{2^r \cdot q} \right)^k$$
2. **Squaring (Recurrence):**
For $j=0$ to $r-1$:
$$P_{j+1}(t) \leftarrow \Delta^{-1} \cdot (P_j(t))^2$$
This utilizes the property $\exp(2i\theta) = \exp(i\theta)^2$.
3. Visualization of the sine wave vanishing at every period $q$, and the slope of the tangent line is $1$.

### Step 4: Apply the sine function on the slots.

#### Setup
- $ct(X)$ encrypting $[t_0, t_1, \cdots, t_{N-1}]$
- Assume the modular reduction function is a Talyor polynomial $P(X) = X - \frac{X^3}{6}$
#### Execution
- step 1: calculate $X\rightarrow ct(X)$
- Slot View: $[t_0, t_1, \cdots, t_{N-1}]$)
- step 2: calculate $X^3\rightarrow ct(X)\cdot ct(X)\cdot ct(X)$
- Slot View: $[t_0^3, t_1^3, \cdots, t_{N-1}^3]$
- step 3: calculate $X^3/6\rightarrow ct(X)\cdot ct(X)\cdot ct(X)/6$
- Slot View: $[\frac{t_0^3}{6}, \frac{t_0^3}{6}, \cdots, \frac{t_{N-1}^3}{6}]$
- step 4: calculate $X-X^3/6=ct(X)-ct(X)\cdot ct(X)\cdot ct(X)/6$
- Slot View: $[t_0-\frac{t_0^3}{6}, t_1-\frac{t_0^3}{6}, \cdots, t_{N-1}-\frac{t_{N-1}^3}{6}]$
- Output $ct_{final}=X-X^3/6$ encrypting the slots which the modular reduction function applied on.

### **Step 5: ImgExt (Imaginary Extraction)**
- Extract the sine component from the complex exponential.
We know that $\sin(\theta) = \frac{1}{2i}(e^{i\theta} - e^{-i\theta})$.
We compute:
$$\frac{q}{2\pi} \sin\left(\frac{2\pi m}{q}\right) \approx m$$
Homomorphically, this uses the **Conjugation** operation:
$$\sin\left(\frac{2\pi m}{q}\right) = \frac{1}{2} \left( \exp\left(\frac{2\pi i m}{q}\right) - \overline{\exp\left(\frac{2\pi i m}{q}\right)} \right)$$

### **Step 6: SlotToCoeff (Inverse Linear Transformation)**
- Repack the recovered message coefficients $t_j$ from the slots back into the polynomial coefficient representation.
- This is the inverse of Step 2. It maps the slot vectors $z_0, z_1$ back to the polynomial $t(X)$ using linear transformations defined by the sub-matrices $U_0$ and $U_1$.

## Diagram Summary

## Reference
- [Bootstrapping for Approximate Homomorphic Encryption](https://eprint.iacr.org/2018/153)
- [CKKS Performance Today from Damien Stehle](https://www.youtube.com/watch?v=Zl1lVxQyj60)
- [Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys](https://www.youtube.com/watch?v=6GCA3Nv1ZYs)

## Further Reading
- [Improved Bootstrapping for Approximate Homomorphic Encryption](https://eprint.iacr.org/2018/1043)
- [Better Bootstrapping for Approximate Homomorphic Encryption](https://eprint.iacr.org/2019/688)
- [High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function](https://eprint.iacr.org/2020/552)