# XI. Rescaling

[TOC]

## Introduction
This is the eleventh chapter of our [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. In the [previous chapter](https://hackmd.io/A-Cz0U64Qxu2jkuCFQppyA), we introduced **relinearization**, which transforms the term $d_2 \cdot s^2$ into a new ciphertext that is linear in $s$. In this chapter, we address the remaining challenge—the **squared scaling factor**—by introducing the technique of **rescaling**.

## **Notations**
- **$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)$.
- **$\mathcal{C_l} = \{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$.
- **$P$**: The product of the auxiliary basis, $P = \prod_{i=0}^{k-1} p_i$.
- **$[a]_{\mathcal{C}}$**: The RNS representation of polynomial $a$ in basis $\mathcal{C}$
- i.e., a vector $(a \pmod{q_0}, \dots, a \pmod{q_{l}})$.

## Where are we at now ?
Multiplication of $c_1$ & $c_2$
$$(b_1 + a_1 s) \cdot (b_2 + a_2 s) = (\Delta m_1+e_1) \cdot (\Delta m_2+e_2)\approx\Delta^2m_1m_2$$
Expanding the right hand side:
$$
\Delta^2m_1m_2 + e_{mult}=\underbrace{\Delta^2 m_1 m_2}_{\text{Scaled Message}} + \underbrace{\Delta m_1 e_2 + \Delta m_2 e_1 + e_1 e_2}_{e_{mult}}
$$
After relinearization, we have:
$$c_2=(c_0, c_1)\rightarrow c_1+c_0\cdot s=\Delta^2m_1m_2+e_{mult} \pmod{Q_l}$$
In RNS domain, this is equivalent to
$$[c_2]_{\mathcal{C_l}}=\left([c_0]_{\mathcal{C_l}}, [c_1]_{\mathcal{C_l}} \right)\rightarrow[c_0]_{\mathcal{C_l}}+[c_1]_{\mathcal{C_l}}\odot[\mathcal{s}]_{\mathcal{C_l}}=[\Delta^2m_1m_2+e_{mult}]_{\mathcal{C_l}}$$

## Rescaling
Modulus Switching in non-RNS domain: $Q_l \rightarrow Q_{l-1}=Q_l/q_l$,
- From $Q_l$:
$$c_2=(c_0, c_1)\rightarrow c_1+c_0\cdot s=\Delta^2m_1m_2+e_{mult} \pmod{Q_l}$$
- To $Q_{l-1}:$
$$\lfloor c_2/q_l\rceil=(\lfloor c_0/q_l\rceil, \lfloor c_1/q_l\rceil)\rightarrow \lfloor (c_1+c_0\cdot s)/q_l\rceil \approx\lfloor\Delta^2/q_l\rceil m_1m_2+\lfloor e_{mult}/q_l\rceil \pmod{Q_l/q_l}$$
- Observe that if $\Delta\approx q_l$, the right hand side will be
$$\lfloor (c_1+c_0\cdot s)/q_l\rceil \approx\Delta m_1m_2+\lfloor e_{mult}/q_l\rceil \pmod{Q_l/q_l}$$
remains to be a valid ciphertext form, and we can decrypt it without non-squared scaling factor domain.

## Example of rescaling in non-RNS domain
### 1. Setup Parameters

We define the polynomial ring $\mathcal{R} = \mathbb{Z}[X]/(X^4 + 1)$.

- Scaling Factor / Modulus to drop $q_l$: $2083$
- Next Modulus $Q_{l-1}$: $2081$
- Current Modulus $Q_l$: $Q_l = 2083 \times 2081 = 4,334,723$
- Scaling Factor $\Delta$: Let $\Delta = q_l = 2083$
- Secret Key $s$: $s(x) = x$

### 2. Messages and Polynomials

Let our two messages be simple polynomials:
- $m_1(x) = 3 + 2x$
- $m_2(x) = 1 - 4x$

Construct the message in ciphertext:
$$\Delta^2 m_1 m_2 = 2083^2 (3+2x)(1-4x) = 4,338,889(3 - 10x - 8x^2)$$

### 3. Construct a ciphertext $c_2 = (c_0, c_1)$
Let the original noise be $$e_{mult} = 10 + 5x$$

The decryption equation $V$ at level $l$ is:
\begin{align}
V &= c_1 + c_0 s &\pmod{Q_l} \\
&= \Delta^2 m_1 m_2 + e_{mult} &\pmod{Q_l} \\
&= 13,016,667 - 43,388,890x - 34,711,112x^2 + (10 + 5x) &\pmod{Q_l}\\
&= 13,016,677 - 43,388,885x - 34,711,112x^2 &\pmod{Q_l}
\end{align}

Let $c_0=20,000x$, the ciphertext $c_2=(c_0, c_1)$ at $Q_l$
$$c_2 = (c_0, c_1) = (20,000x, \; 12,508 + 4,293,068x + 4,281,395x^2)$$

---

### 4. Modulus Switching: From $Q_{l}$ To $Q_{l-1}$

We now perform the rescaling operation: $\lfloor c / q_l \rceil$. We divide every coefficient by $q_l = 2083$ and round to the nearest integer.
- Scale $c_0$
$$c'_0 = \lfloor 20,000 / 2083 \rceil x \approx \lfloor 9.601\rceil x = \mathbf{10x}$$
- Scale $c_1$
$$c_1'=\lfloor12,508/2083\rceil + \lfloor4293068/2083\rceil x + \lfloor4,281,395/2083\rceil x^2=6+2061x+2055x^2$$

**The Rescaled Ciphertext at $Q_{l-1}$:**
$$c'_{2} = (c'_0, c'_1) = (10x, \;\; 6 + 2061x + 2,055x^2)$$

---

### **5. Observation and Verification**

Now we check if the new ciphertext decrypts to $\Delta m_1 m_2$ modulo the new modulus $Q_{l-1} = 2081$. We have a new decryption result $M_{new}$
\begin{align}
M_{new} &= c'_1 + c'_0\cdot s \\
&= 6 + 2061x + 2055x^2 + 10x\cdot x \\
&= 6 + 2061x + 2065x^2 \\
&\stackrel{?}{\approx} \Delta m_1 m_2 \pmod{Q_{l-1}=2081}
\end{align}

Convert the coefficients to symmetric modulo $2081$ in range $[-1040, 1040]$:
$$M_{new} \equiv 6 - 20x - 16x^2 \pmod{2081}$$

### 6. Verify if $M_{new}\approx \Delta m_1 m_2$
Recall $m_1 m_2 = 3 - 10x - 8x^2$.
$$\Delta m_1 m_2 = 2083(3 - 10x - 8x^2) = 6249 - 20830x - 16664x^2$$

Reduce expected result modulo $Q_{l-1} = 2081$:
$$\Delta m_1 m_2 = 6249 - 20830x - 16664x^2=6 -20 x -16x^2 \pmod{2081}$$

$$\Rightarrow M_{new}=\Delta m_1 m_2 = 6 -20 x -16x^2 \pmod{2081}$$

In most of the time, since the scaling factor $\Delta$ is just approximate to the moduli $q_l$, $M_{new}$ and $\Delta m_1 m_2$ are exactly the same.
## Rescaling in RNS domain

### Overview
- **Input:**
- Ciphertext: $[c_2]_{\mathcal{C_l}}=\left([c_0]_{\mathcal{C_l}}, [c_1]_{\mathcal{C_l}} \right)$ at level $l$ in RNS domain.
- Current Modulus $Q_l=\prod_{i=0}^lq_i$
- Modulus to drop: $q_l$ (the last prime in the chain).
- **Reduction algorithm:**
- For each remaining modulus $q_j$ (where $j < l$):
$$c_2'^{(j)} \leftarrow (c_2^{(j)} - c_2^{(l)}) \cdot q_l^{-1} \pmod{q_j}$$
- See below for the details.
- **Result:**
- This effectively computes $\lfloor c_2 / q_l \rfloor$ in the RNS domain by subtracting the part associated with $q_l$ and multiplying by its inverse in the other components.

### Reduction algorithm
- **Identify the Remainder:**
Look at the component corresponding to the modulus we are about to drop: $c_2^{(l)}$.
In the integer domain, any number $X$ can be written as $$X = k \cdot q_l + (X \pmod{q_l})$$
Therefore, $X - (X \pmod{q_l})$ is perfectly divisible by $q_l$.
- **Compute Difference & Divide (Component-wise):**
We cannot simply "drop" the index $l$. We must update all *other* indices ($0 \le j < l$) to reflect the division by $q_l$.

For every remaining modulus $q_j$ (where $j = 0$ to $l-1$), calculate:
$$c_2'^{(j)} = (c_2^{(j)} - c_2^{(l)}) \cdot [q_l^{-1}]_{q_j} \pmod{q_j}$$

- **$c^{(j)}$**: The value in the current basis.
- **$c^{(l)}$**: The value in the basis being dropped (treated here as the "remainder").
- **$[q_l^{-1}]_{q_j}$**:
- The modular inverse of the dropped prime modulo the current prime $q_j$. Note that This inverse exists because $q_l$ and $q_j$ are coprime.
- **Output:**
The new ciphertext polynomials are composed of the updated components:
$$c_2' = (c_2'^{(0)}, \dots, c_2'^{(l-1)})$$
The component $c^{(l)}$ is discarded. The level is reduced to $l-1$.

---

### Mathematical Logic: Why this works?

Let $X$ be the integer polynomial represented by the RNS vector. We want to compute $X' \approx X / q_l$. The arithmetic operation $c'^{(j)} = (c^{(j)} - c^{(l)}) \cdot q_l^{-1} \pmod{q_j}$ is actually computing the RNS representation of:
$$\frac{X - (X \pmod{q_l})}{q_l}$$

- $X - (X \pmod{q_l})$ subtracts the remainder, finding the nearest integer to $X$ that is strictly divisible by $q_l$ (rounding down to the nearest multiple).
- Multiplying by $q_l^{-1}$ divides that nearest multiple by $q_l$.

This results in a new integer that effectively "scales down" the message by the factor $q_l$, while maintaining consistency across the remaining RNS bases.

## Example of Rescaling in RNS
### Setup
- RNS Basis: $\mathcal{C} = \{q_0, q_1\} = \{3, 5\}$.
- Total Modulus: $Q = 3 \times 5 = 15$.
- Scale Factor to Drop: $q_1 = 5$.
- Inverse of $q_1 \pmod{q_0}$:
- $q_1^{-1} \pmod{q_0}=5^{-1} \pmod 3=2$.

### Scenario
We have an encrypted value representing the integer 13.
* We want to rescale 13 by 5.
* Expected Integer Result: $\lfloor 13 / 5 \rfloor = 2$ (or rounding to nearest, but let's look at the integer arithmetic).
* Specifically, the formula computes $(13 - (13 \pmod 5)) / 5 = (13 - 3) / 5 = 2$.

### Execution in RNS

1. **Input Vector ($c$) for 13:**
* $c^{(0)} = 13 \pmod 3 = 1$
* $c^{(1)} = 13 \pmod 5 = 3$ (This is the remainder we drop).
2. **Apply Formula:**
$$c'^{(0)} = (c^{(0)} - c^{(1)}) \cdot q_1^{-1} \pmod{q_0}=(1 - 3) \cdot 2 \pmod 3$$
3. **Verification:**
* The result in RNS basis $\{3\}$ is **2**.
* The expected integer result was **2**.
* $2 \pmod 3 = 2$. **Success.**

The value 13 represented as $[1, 3]$, has been successfully rescaled to $[2]$ by dropping the second modulus, using only modular arithmetic. In the full RNS variant, this must be done without reconstructing the large integer.

## Conclusion
In the Full RNS Variant of CKKS, the size of the scaling factor and the size of the primes in the moduli chain **must be approximately equal**.

$$q_i \approx \text{Scaling Factor } (q)$$

This relationship is not arbitrary; it is a functional requirement for the **Rescaling** operation to work as a valid rounding step. If $q_l \gg \Delta$ or $q_l \ll \Delta$, the resulting message would have an incorrect scale, destroying the fixed-point representation.

#### Bit-Size & Precision
- **High Precision:** If you need 50 bits of precision for your data, you must choose a scaling factor $q \approx 2^{50}$. Consequently, every prime $q_i$ in your chain must be a 50-bit integer.
- **Low Precision:** If you only need 20 bits, you can use 20-bit primes.

#### Depth vs. Security Trade-off
This relationship creates a strict budget for computation:
* **Total Capacity:** The security level fixes the maximum size of the total modulus $Q_{total} = q_0 \cdot q_1 \cdots q_L$.
* **The Trade-off:** Since $q_i \approx \text{Scale}$, a larger scaling factor "consumes" more bits of the total modulus budget per level.
* **Larger Scale ($q$)** $\rightarrow$ Higher Precision $\rightarrow$ Fewer Levels ($L$) available (shallower circuits).
* **Smaller Scale ($q$)** $\rightarrow$ Lower Precision $\rightarrow$ More Levels ($L$) available (deeper circuits).

📌 In practical, $L$ ranges from 30 to 45.
#### The "Approximate" Characteristic
Unlike the original CKKS which used exact powers of 2 ($q_i = 2^p$), the RNS variant uses primes. Since prime numbers cannot exactly match a power of 2, we have:
$$q_i \in (q \cdot (1-\epsilon), q \cdot (1+\epsilon))$$
This slight mismatch between the "ideal" scale and the "actual" prime modulus $q_i$ is the source of the slight approximation error added during every Rescaling step in the RNS-CKKS scheme.