# IX. Modulus Switching

[TOC]

## Introduction
This is the ninth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. In the [previous chapter](https://hackmd.io/U3qaUOl1RzGm2pkhG8VkDg), we identified two technical challenges: (i) the term $d_2 \cdot s^2$ must be reduced to something linear in $s$ to form a valid RLWE ciphertext encrypted under the secret key $s$, and (ii) the scaling factor $\Delta^2$ must be controlled during homomorphic multiplication. These issues are addressed by **relinearization** and **rescaling**, respectively.

Before diving into these mechanisms, recall that the ciphertext modulus $Q$ in polynomial rings typically exceeds $2^{2000}$, making direct arithmetic prohibitively expensive. To mitigate this cost, CKKS employs the [**Residue Number System (RNS)**](https://en.wikipedia.org/wiki/Residue_number_system), grounded in the **Chinese Remainder Theorem (CRT)**, to decompose large-modulus operations into many small-modulus ones. This chapter introduces the **modulus switching** in RNS domain, which is heavily used by **relinearization** and **rescaling**.

## **Notations**
- **$\lambda$**: Security parameter.
- **$N$**: The degree of the polynomial quotient ring , and is power of two integer.
- **$\mathcal{R}$**: The ring of integers $\mathbb{Z}[X]/(X^N+1)$.
- **$\Delta$**: The target scale factor (base integer) for fixed-point arithmetic.
- **$\mathcal{C} = \{q_0, \dots, q_L\}$**: The chain of RNS moduli where $q_i \approx q$.
- **$Q_l$**: The ciphertext modulus at current level $l$, defined as $Q_l = \prod_{i=0}^l q_i$.
- **$\mathcal{B} = \{p_0, \dots, p_{k-1}\}$**: Auxiliary RNS basis (special primes) used for key-switching, coprime to $\mathcal{C}$.
- **$P$**: The product of the auxiliary basis, $P = \prod_{i=0}^{k-1} p_i$.
- **$[a]_{\mathcal{C}}$**: The RNS representation of integer or poylnomial $a$ in basis $\mathcal{C}$
- i.e., a vector $(a \pmod{q_0}, \dots, a \pmod{q_{l}})$.
- **$[a]_{\mathcal{B}}$**: The RNS representation of integer or poylnomial $a$ in basis $\mathcal{B}$
- i.e., a vector $(a \pmod{p_0}, \dots, a \pmod{p_{k-1}})$.
- **$\text{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}$**: Fast basis conversion algorithm that converts an RNS representation from basis $\mathcal{C}$ to basis $\mathcal{B}$.

## Modulus Switching
Before entering relinearization and rescaling, we have to know **Approximate Modulus Switching**. The scheme handles non-arithmetic operations, such as rounding and scaling, within the RNS domain. We also provide examples for better understanding.

Note that although RNS is typically introduced using integers, CKKS operates on polynomials. The transition is straightforward: RNS is simply applied coefficient-wise, and no structural changes occur in the polynomial operations.

The modulus switching is essentially mapping a number from a modular domain to another one. In RNS Domain, we call this **Basis Conversion**. For example:
\begin{align}
&10000 \pmod{3\cdot 5} = 10 \\
\rightarrow &10000 \pmod{7\cdot11}=67
\end{align}

### Fast Basis Conversion ($\text{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}$)
- Convert a number represented in basis $\mathcal{C}$ to basis $\mathcal{B}$ without fully reconstructing the large integer.
- **Input:**
- $[a]_{\mathcal{C}} = (a^{(0)}, \dots, a^{(l)})$ where $a \in \mathbb{Z}_Q$.
- **Calculation:**
- It computes the approximate basis conversion using the CRT formula:
$$\text{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}([a]_{\mathcal{C}}) = \sum_{j=0}^{l-1} \left[ a^{(j)} \cdot \hat{q}_j^{-1} \right]_{q_j} \cdot \hat{q}_j \pmod{p_i}$$ where $\hat{q}_j = Q/q_j$.
- **Output:**
- The RNS representation of $a + Q \cdot e$ in basis $\mathcal{B}$ for some small error $e$, effectively switching the basis while keeping the value congruent modulo $Q$.

### Approximate Modulus Raising (ModUp)
- Given $[a]_\mathcal{C}$ (representation in $Q$), find $[a]_{\mathcal{D}}$ (representation in $P \cdot Q$) such that the value is approximately the same. This algorithm is used during homomorphic multiplication to raise the modulus from $Q$ to $P \cdot Q$ to enable key switching.
- **Input:**
- RNS vector in basis $\mathcal{C}$ ($a^{(0)}, \dots, a^{(l)}$).
- **Basis Conversion:**
- Run $\text{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}$ to get the components for the $\mathcal{B}$ basis ($\tilde{a}^{(0)}, \dots, \tilde{a}^{(k-1)}$).
- **Concatenation:**
- Combine the original input and the converted result:
$$\text{ModUp}([a]_\mathcal{C}) = (\tilde{a}^{(0)}, \dots, \tilde{a}^{(k-1)}, a^{(0)}, \dots, a^{(l)})$$
- **Result:**
- This represents $a + Q \cdot e$ in the full basis $\mathcal{D} = \mathcal{B} \cup \mathcal{C}$.

### Approximate Modulus Reduction (ModDown)
- Given $[b]_{\mathcal{D}}$ (large modulus $P \cdot Q$), compute $[b']_{\mathcal{C}}$ (small modulus $Q$) such that $b' \approx P^{-1} \cdot b$. This algorithm is used after key switching to reduce the modulus from $P \cdot Q$ back to $Q$ and scale down the noise.
- **Input:**
- $[b]_{\mathcal{D}} = (\tilde{b}^{(0)}, \dots, \tilde{b}^{(k-1)}, b^{(0)}, \dots, b^{(l)})$.
- **Basis Conversion:**
- Compute the "error" part using the auxiliary basis $\mathcal{B}$:
$(\tilde{a}^{(0)}, \dots, \tilde{a}^{(l-1)}) \leftarrow \text{Conv}_{\mathcal{B} \rightarrow \mathcal{C}}(\tilde{b}^{(0)}, \dots, \tilde{b}^{(k-1)})$
- **Correction & Scaling:**
- Compute the result in basis $\mathcal{C}$, for each $j \in [0, l]$:
$$b'^{(j)} = (b^{(j)} - \tilde{a}^{(j)}) \cdot [P^{-1}]_{q_j} \pmod{q_j}$$
- **Result:**
- Returns the RNS representation of a value close to $b/P$.

## Examples of modulus Switching
### Parameters Setup
- Basis $\mathcal{C}$ (Ciphertext Basis):
- Primes: $\mathcal{C} = \{13, 17, 19\}$
- Product: $Q = 13 \times 17 \times 19 = \mathbf{4,199}$
- Basis $\mathcal{B}$ (Special Prime Basis):
- Primes: $\mathcal{B} = \{23, 29, 31\}$
- Product: $P = 23 \times 29 \times 31 = \mathbf{20,677}$
- Overall Modulus: $P \cdot Q = 86,822,723$

---
### Fast Basis Conversion

This algorithm $\text{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}$ converts the RNS representation of a number $a$ from basis $\mathcal{C}$ to basis $\mathcal{B}$ without computing the full integer $a$.

#### Step 2. Input
- Input $[a]_{\mathcal{C}}=[1234]_{\mathcal{C}}=[12,10,18]$
- $1234 \pmod{13} = \mathbf{12}$
- $1234 \pmod{17} = \mathbf{10}$
- $1234 \pmod{19} = \mathbf{18}$

#### Step 2. Conversion
- The formula is $[a]_{\mathcal{B}} = \sum_{j=0}^{2} \left[ a^{(j)} \cdot \hat{q}_j^{-1} \right]_{q_j} \cdot \hat{q}_j \pmod{p_i}$
- Calculate Weights ($\hat{q}_j$):
- $\hat{q}_0 = Q/13 = 323$, and $\hat{q}_0^{-1} \equiv 323^{-1} \equiv 11^{-1} \equiv 6 \pmod{13}$.
- $\hat{q}_1 = Q/17 = 247$, and $\hat{q}_1^{-1} \equiv 247^{-1} \equiv 9^{-1} \equiv 2 \pmod{17}$.
- $\hat{q}_2 = Q/19 = 221$, and $\hat{q}_2^{-1} \equiv 221^{-1} \equiv 12^{-1} \equiv 8 \pmod{19}$.
- Compute Terms ($\alpha_j$):
- $\alpha_0 = [a^{(0)}\cdot\hat{q}_0^{-1}]_{q_0} = 12 \times 6 = \mathbf{7} \pmod{13}$
- $\alpha_1 = [a^{(1)}\cdot\hat{q}_1^{-1}]_{q_1} = 10 \times 2 = \mathbf{3} \pmod{17}$
- $\alpha_2 = [a^{(2)}\cdot\hat{q}_2^{-1}]_{q_2} = 18 \times 8 = \mathbf{11} \pmod{19}$

#### Step 3. Output
- Output $[a]_{\mathcal{B}}=[5, 10, 8]$:
- Sum $= (7 \cdot 323 + 3 \cdot 247 + 11 \cdot 221) =5\pmod{23}$
- Sum $= (7 \cdot 323 + 3 \cdot 247 + 11 \cdot 221) =10\pmod{29}$
- Sum $= (7 \cdot 323 + 3 \cdot 247 + 11 \cdot 221) =8\pmod{31}$

#### Step 4. Verification
- The integer constructed by the CRT formula is 5,433. Note that $5433 \equiv 1234 \pmod{4199}$. The conversion is correct.

-----
### Approximate Modulus Raising (ModUp)

This alogrithm transforms a ciphertext from modulus $Q$ to $P \cdot Q$ to enable key switching. Following above parameter setup, we want to raise the modulus of **$a = 1,234$** from $\mathcal{C}$ to $\mathcal{D} = \mathcal{C} \cup \mathcal{B}$.

#### Step 1. Input
- Input $[a]_{\mathcal{C}}=[1234]_{\mathcal{C}}=[12,10,18]$

#### Step 2. Conversion
- **Basis Conversion:** Run $\text{Conv}_{\mathcal{C} \rightarrow \mathcal{B}}$ on the input. The result is $[5, 10, 8]$.
- **Concatenate:** simply append the original input to the converted result.

#### Step 3. Output
- Output $[a]_{\mathcal{D}}=[a]_{\mathcal{C} \,\cup\, \mathcal{B}}=[5, 10, 8, 12, 10, 18]$

#### Step 4. Observation
- This vector represents the integer **5,433** in the combined basis $\mathcal{D}$. The value is congruent to $1,234 \pmod Q$ but now exists in the larger ring $R_{P \cdot Q}$.

-----
### Approximate Modulus Reduction (ModDown)

This scales a number down by $P$ and switches back to modulus $Q$. It effectively computes $\approx Y/P$. For example, We start with a large number $Y = \mathbf{2,500,000}$. We want to compute $Y / P = 2,500,000 / 20,677 \approx \mathbf{120.9}$ without directly working on $Y$.

#### Step 1. Input
- Input $[Y]_{\mathcal{D}}=[15, 26, 5, 9, 14, 18]$
- $\mathcal{B}$ part ($[Y]_{\mathcal{B}}) = [15, 26, 5]$
- $\mathcal{C}$ part ($[Y]_{\mathcal{C}}) = [9, 14, 18]$

#### Step 2. Conversion
- **Fast Basis Conversion ($\text{Conv}_{\mathcal{B} \rightarrow \mathcal{C}}$):**
- Convert the $[Y]_{\mathcal{B}}$=$[15, 26, 5]$ into basis $\mathcal{C}$.
- Output: ($[\tilde{a}]_{\mathcal{C}})=[8, 14, 12]$
- *Note: This represents an integer $A \approx 39,437$, which is congruent to $Y \pmod P$.*
- **Subtract and Scale:**
- Precompute $[P^{-1}]_{\mathcal{C}}=[2,7,4]$
- $20677^{-1} \equiv 2 \pmod{13}$
- $20677^{-1} \equiv 7 \pmod{17}$
- $20677^{-1} \equiv 4 \pmod{19}$
- Compute $([Y]_{\mathcal{q_j}} - [\tilde{a}]_{\mathcal{q_j}}) \cdot P^{-1} \pmod{q_j}$ for each $q_j \in \mathcal{C}$.
- $([Y]_{\mathcal{q_0}} - [\tilde{a}]_{\mathcal{q_0}}) \cdot P^{-1}=(9-8) \times 2 = 2 \pmod{13}$
- $([Y]_{\mathcal{q_1}} - [\tilde{a}]_{\mathcal{q_1}}) \cdot P^{-1}=(14-14) \times 7 = 0 \pmod{17}$
- $([Y]_{\mathcal{q_2}} - [\tilde{a}]_{\mathcal{q_2}}) \cdot P^{-1}=(18-12) \times 4 = 5 \pmod{19}$
#### Step 3. Output
- Output: $[Y-\tilde{a}]_{\mathcal{C}} \cdot P^{-1}=[2, 0, 5]$

#### Step 4. Verification
- By CRT, this output RNS vector corresponds to the integer **119**.
- $119 \equiv 2 \pmod{13}$
- $119 \equiv 0 \pmod{17}$
- $119 \equiv 5 \pmod{19}$
- The algorithm output **119**, which is close to the expected result $120.9$. The tiny precision loss can be viewed as the error of a ciphtertext.