# X. Relinearization

[TOC]

## Introduction
This is the tenth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. In the [previous chapter](https://hackmd.io/U3qaUOl1RzGm2pkhG8VkDg), we identified two technical challenges:
1. 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$
2. The scaling factor $\Delta^2$ must be controlled during homomorphic multiplication.

These issues are addressed by relinearization and rescaling, respectively. In this chapter, we explain the process of relinearization of $d_2\cdots^2$ and leave the rescaling of $\Delta^2$ to next chapter.

## **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)$.
- **$q$**: 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 polynomial $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 polynomial $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}$.

## Relinearization
- Recall that the multiplication of two ciphertexts produces
$$
(b_1 + a_1 s)(b_2 + a_2 s) = d_0 + d_1 s + d_2 s^2=\Delta^2m_1m_2+e_{mult} \pmod Q
$$
This multiplication is straightforward, but $P$ and $Q$ is really big, we compute relinearization in RNS domain to mitigate the heavy workload. Relinearization transforms this back to a ciphertext corresponding to the secret key $s$.

---
### Definitions
- **Input Ciphertexts:**
- $c_0 = (a_0, b_0)\pmod{Q_l = \prod_{j=0}^l q_j}$
- $c_1 = (a_1, b_1) \pmod{Q_l = \prod_{j=0}^l q_j}$
- **Bases:**
- $\mathcal{C}_l = \{q_0, \dots, q_l\}$: The current ciphertext modulus basis at level $l$.
- $\mathcal{B} = \{p_0, \dots, p_{k-1}\}$: The auxiliary "special prime" basis used for key switching.
- $P = \prod_{i=0}^{k-1} p_i$
- $Q_l = \prod_{j=0}^{l} q_j$.
- $\mathcal{D}_l = \mathcal{B} \cup \mathcal{C}_l$: The extended basis ($P \cdot Q_l$).
- **Evaluation Key $evk$:**
- A special key generated by $KSKGen(s^2, s)$ used to convert terms with $s^2$ back to terms with $s$. It is essentially an encryption of $P \cdot s^2$ stored in the large basis $\mathcal{D_l} = \mathcal{B} \cup \mathcal{C}_l$
- Rewrite the secret keys into RNS form, we don't have modup $s$ to get $[s]_{\mathcal{D_l}}$ since we know $s$ before reduced by anything.
- $[s]_{\mathcal{D_l}}=(s^{(0)}, ...,s^{(k-1)}, s^{(k)}, ...,s^{(k+l)})$
- $[s^2]_{\mathcal{D_l}}=\left((s^{(0)})^2, ...,(s^{(k-1)})^2, (s^{(k)})^2, ...,(s^{(k+l)})^2\right)$

---
### **Step 1: Tensor Product (Arithmetic Multiplication)**
First, the algorithm computes the cross-terms of the two ciphertexts. This corresponds to the polynomial multiplication \begin{align}(b_1 + a_1 s) \cdot (b_2 + a_2 s)
&=b_1 b_2 + (a_1 b_2 + a_2 b_1) \cdot s +(a_1 a_2) \cdot s^2 \\
&=d_0 + d_1 s + d_2 s^2
\end{align}

For each RNS component $j$ (where $0 \le j \le l$), compute:
- Constant term:
- $[d_0]_{\mathcal{Q_l}}=(d_0^{(0)},d_0^{(1)}, ..., d_0^{(l)})$, where $d_0^{(j)}=b_0^{(j)} b_1^{(j)} \pmod{q_j}$
- Linear term:
- $[d_1]_{\mathcal{Q_l}}=(d_1^{(0)},d_1^{(1)}, ..., d_1^{(l)})$, where $d_1^{(j)}=a_1^{(j)} b_2^{(j)} + a_2^{(j)} b_1^{(j)} \pmod{q_j}$
- Quadratic term:
- $[d_2]_{\mathcal{Q_l}}=(d_2^{(0)},d_2^{(1)}, ..., d_2^{(l)})$, where $d_2^{(j)}=a_1^{(j)} a_2^{(j)} \pmod{q_j}$

---
### **Step 2: Approximate Modulus Raising (ModUp)**
Raise the modulus of the term $d_2$ from modulus $Q_l$ to larger modulus $P \cdot Q_l$. The algorithm executes $\text{ModUp}_{\mathcal{C}_l \rightarrow \mathcal{D}_l}(d_2)$:

#### **Fast Basis Conversion:**
- Convert the RNS representation of $d_2$ from basis $\mathcal{C}_l$ to basis $\mathcal{B}$.
$$(\tilde{d}_2^{(0)}, \dots, \tilde{d}_2^{(k-1)}) \leftarrow \text{Conv}_{\mathcal{C}_l \rightarrow \mathcal{B}}(d_2^{(0)}, \dots, d_2^{(l)})$$
This calculates values modulo $p_i$ that are congruent to the original $d_2$ modulo $Q_l$
#### **Combine:**
- The result is a vector in the full basis $\mathcal{D}_l$:
$$[\tilde{d}_2]_{\mathcal{D_l}} = (\underbrace{\tilde{d}_2^{(0)}, \dots, \tilde{d}_2^{(k-1)}}_{\text{basis } \mathcal{B}}, \underbrace{d_2^{(0)}, \dots, d_2^{(l)}}_{\text{basis } \mathcal{C}_l})$$

---
### **Step 3. Key-Switching Key Generation ($KSKGen$)**
#### RLWE Ciphertext samples:
- Sample random polynomial $a'$ from a uniform distribution.
$$[a']_{\mathcal{D_l}} = (a'^{(0)}, \dots, a'^{(k+L)}) \leftarrow \text{Uniform}\left(\prod_{i=0}^{k-1} \mathcal{R}_{p_i} \times \prod_{j=0}^{L} \mathcal{R}_{q_j}\right)$$
- Sample small error polynomial $e'$ from a discrete gaussian distribution $\chi_{err}$.
$$[e']_{\mathcal{D_l}} = (e'^{(0)}, \dots, e'^{(k+L)}) \leftarrow \text{DiscreteGaussian}\left(\prod_{i=0}^{k-1} \mathcal{R}_{p_i} \times \prod_{j=0}^{L} \mathcal{R}_{q_j}\right)$$
- Calculate $b'$ such that the pair $(b', a')$ forms an encryption of $P \cdot s^2$ under the key $s$:
$$[b']_{\mathcal{D_l}} \approx -[a']_{\mathcal{D_l}} \cdot [s]_{\mathcal{D_l}} + P \cdot [s^2]_{\mathcal{D_l}}+[e']_{\mathcal{D_l}}$$

- Since the term $P \cdot s_1$ contains the factor $P$, which is a multiple of every $p_i$, it vanishes modulo $p_i$.
$$b'^{(i)} \leftarrow -a'^{(i)} \cdot s^{(i)} + e' \pmod{p_i} \quad \text{for } 0 \le i < k$$
- Use precomputed constants $[P]_{q_j}$
$$b'^{(k+j)} \leftarrow -a'^{(k+j)} \cdot s^{(k+j)} + [P]_{q_j} \cdot (s^{(k+j)})^2 + e'^{(k+j)} \pmod{q_j} \quad \text{for } 0 \le j \le L$$

#### Output
- The evaluation key $evk$ is the vector of these RNS pairs:
$$evk = \left( (b'^{(0)}, a'^{(0)}), \dots, (b'^{(k+L)}, a'^{(k+L)}) \right)$$

---
### **Step 4: Key Switching**
Now that $[\tilde{d}_2]_{\mathcal{D}_l}$ is in the extended basis, it is multiplied by the evaluation key $evk$. The $evk$ consists of pairs $(b', a')$ that encrypt $P \cdot s^2$. Compute $\tilde{ct} = (\tilde{c}_0, \tilde{c}_1)$ in the full basis $\mathcal{D}_l$:

#### Component-wise Multiplication:
- For the special primes ($0 \le i < k$):
$$\tilde{ct}^{(i)} = \tilde{d}_2^{(i)} \cdot evk^{(i)}=\tilde{d}_2^{(i)}\cdot (b'^{(i)},\, a'^{(i)}) \pmod{p_i}$$
- For the ciphertext primes ($0 \le j \le l$):
$$\tilde{ct}^{(k+j)} = d_2^{(j)} \cdot evk^{(k+j)}=\tilde{d}_2^{(j)}\cdot (b'^{(k+j)},\, a'^{(k+j)}) \pmod{q_j}$$
- At this stage, $[\tilde{ct}]_{\mathcal{D}_l}$ is an encryption of $P \cdot d_2 \cdot s^2$ modulo $P \cdot Q_l$.
- $[\tilde{ct}]_{\mathcal{D}_l}$ is equivalent to $\tilde{ct}=(\tilde{c_0}, \tilde{c_1})=\left(d_2\cdot a',\, d_2\cdot(a'\cdots+P\cdot d_2\cdot s^2+e')\right)$
- Define $\langle \tilde{d_2}, evk \rangle=d_2(-a's + Ps^2 + e') + d_2 a's = P \cdot d_2 \cdot s^2 + d_2 \cdot e'$

---
### **Step 5: Approximate Modulus Reduction (ModDown)**
The ciphertext is currently scaled by $P$ and sits in a modulus $P \cdot Q_l$ that is too large. The algorithm must reduce it back to $Q_l$ and divide by $P$. The algorithm executes $\text{ModDown}_{\mathcal{D}_l \rightarrow \mathcal{C}_l}$ on both components $\tilde{c}_0$ and $\tilde{c}_1$. Currently, we have$$\tilde{c}_t=(\tilde{c}_0, \tilde{c}_1)=((\tilde{c}_0^{(0)}, ..., \tilde{c}_0^{(k-1)}, \tilde{c}_0^{(k)}, ..., \tilde{c}_0^{(k+l-1)}), (\tilde{c}_1^{(0)}, ..., \tilde{c}_1^{(k-1)}, \tilde{c}_1^{(k)}, ..., \tilde{c}_1^{(k+l-1)}))$$

#### ModDown For $\tilde{c_0}$ and $\tilde{c_1}$:
- **Extract Basis $\mathcal{B}$ part**:
- Extract the components $(\tilde{c}_0^{(0)}, \dots, \tilde{c}_0^{(k-1)})$ and $(\tilde{c}_1^{(0)}, \dots, \tilde{c}_1^{(k-1)})$ corresponding to moduli $p_i$ and $q_j$
- **Basis Conversion:**
- Convert these from basis $\mathcal{B}$ to basis $\mathcal{C}_l$:
- $(\tilde{a}^{(0)}, \dots, \tilde{a}^{(l-1)}) \leftarrow \text{Conv}_{\mathcal{B} \rightarrow \mathcal{C}_l}(\tilde{c}_0^{(0)}, \dots, \tilde{c}_0^{(k-1)})$
- $(\tilde{b}^{(0)}, \dots, \tilde{b}^{(l-1)}) \leftarrow \text{Conv}_{\mathcal{C} \rightarrow \mathcal{C}_l}(\tilde{c}_1^{(0)}, \dots, \tilde{c}_1^{(k-1)})$
- **Subtraction and Scaling:**
- For each $j$ in basis $\mathcal{C}_l$:
- $\hat{c}_0^{(j)} = (\tilde{c}_0^{(k+j)} - \tilde{a}^{(j)}) \cdot [P^{-1}]_{q_j} \pmod{q_j}$
- $\hat{c}_1^{(j)} = (\tilde{c}_1^{(k+j)} - \tilde{b}^{(j)}) \cdot [P^{-1}]_{q_j} \pmod{q_j}$
- Now we have $\hat{c}_t^{(j)}=(\hat{c}_0^{(j)}, \hat{c}_1^{(j)})$ is the original part in basis $\mathcal{C}_l$.
- Multiplying by $P^{-1}$ effectively divides the integer value by $P$.

#### Output
- Output $\hat{c}_t=(\hat{c}_0, \hat{c}_1)$ in basis $\mathcal{C}_l$.
- The decryption of $\hat{c}_t\approx$ $P^{-1}\left(d_2(-a's + Ps^2 + e') + d_2 a'\right) \approx \underbrace{d_2 \cdot s^2}_{target}+\underbrace{P^{-1} \cdot d_2 \cdot e'}_{\text{a new error}}$
- Since the coefficients of $d_2$ is smaller than $P$, so the new error is manageable.

---
### **Step 6: Final Aggregation**
Finally, add the relinearized quadratic term (now linear) back to the terms calculated in [Step 1](#Step-1-Tensor-Product-Arithmetic-Multiplication).

- For each $j$, where $0 \le j \le l$
$$c_{2}^{(j)} \leftarrow \left(\hat{c}_0^{(j)} + d_0^{(j)},\, \hat{c}_1^{(j)} + d_1^{(j)}\right) \pmod{q_j}$$
- 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}}$$

**Result:**
- We get a ciphertext $c_2$ encrypting the product of the original messages, at level $l$, relative to the secret key $s$.

## Discussion
This paper we refer below presents a variant of the **CKKS (HEAAN)** homomorphic encryption scheme optimized for implementation on standard computer systems (64-bit word arithmetic). The original CKKS scheme required multi-precision arithmetic because its ciphertext moduli ($Q_l = q^l$) were powers of a base, which is incompatible with the Residue Number System (RNS).

## Reference
[A Full RNS Variant of Approximate Homomorphic Encryption](https://eprint.iacr.org/2018/931.pdf)