# XVI. Summary of CKKS Scheme

This is the summary of the part 3 in [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. Let's briefly review how CKKS works, and what techniques are used.

## 1. Message Encoding & SIMD
Instead of encrypting a single number into a massive polynomial, CKKS packs multiple complex numbers into one ciphertext. This uses a technique called **SIMD (Single Instruction, Multiple Data)**.
* **Packing:** A single polynomial uses its "slots" to store a vector of $N/2$ complex numbers.
* **Efficiency:** When you perform an operation (like addition) on the ciphertext, it happens to all $N/2$ numbers in the vector simultaneously.

## 2. Homomorphic Additive and Multiplicative Ciphertexts
- An **additive homomorphic** scheme, preserves the addition operation. It allows us to perform an operation on the ciphertexts (let's call it $\oplus$) that corresponds to addition on the plaintexts:
$$E(m_1) \oplus E(m_2) = E(m_1 + m_2)$$
Adding two ciphertexts adds their underlying message vectors component-wise.
- A **multiplicative homomorphic** scheme (like Elgamal Encryption) does the same for multiplication, using an operation $\otimes$:
$$E(m_1) \otimes E(m_2) = E(m_1 \times m_2)$$
Multiplying two ciphertexts is equivalent to multiply their message vectors component-wise. This operation increases the noise in the ciphertext significantly.
## 3. Modulus Switching
Modulus switching is the process of changing the modulus associated with the ciphertext, generating a quite amount of error. This operation is used by the following operations below. Modulus switching in RNS domain is accomplished by using **Fast Basis Conversion**.
$$\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}$$

## 4. Relinearization
Multipling two ciphertexts (each consisting of 2 polynomials) expands to 3 polynomials ($d_0, d_1, d_2$), where $d_2$ contains a term $s^2$.
$$(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$$
Relinearization uses a special "Evaluation Key" ($evk$) to relinearize $d_2$ with respect to $s$ and compress these 3 polynomials back down to the standard 2, allowing further operations.

## 5. Rescaling
Multiplying two numbers makes the product of messages scaled by $\Delta^2$ instead of $\Delta$.
$$(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$$
Therefore, we use modulus switching to scale the message down by $\Delta$. Rescaling divides the ciphertext by the factor $q_i$, where $q_i\approx \Delta$ and effectively "chops off" the extra scale and some noise. This operation relies on the **Approximate Modulus Reduction** based on **Modulus Switching**.

## 6. Homomorphic Rotation
Since additions and multiplicatiosn happen slot-wise, the numbers in different slots cannot interact directly. Homomorphic Rotation fixes this. It cyclically shifts the vector of numbers in the encrypted slots (e.g., moving the values in slot left by 1). That a ciphertext $ct(X)$ encrpyting slots:
$$[m(\zeta^1), m(\zeta^5), m(\zeta^9), m(\zeta^{13})]=[10,20,30,40]$$
After homomorphic rotation, we have a new ciphertext $ct_{new}(X)$ encrypting
$$[m(\zeta^5), m(\zeta^9), m(\zeta^{13}), m(\zeta^1), ]=[20, 30, 40, 10]$$

## 7. Homomorphic Conjugation
This operation computes the complex conjugate of every number in the vector slots (changing $a+b\cdot i$ to $a-b\cdot i$). It is essential for extracting the real or imaginary parts of a number and for computing linear transformations. Similar to rotation, it uses a specific key-switching operation corresponding to $X \mapsto X^{-1}$.

## 8. Homomorphic Matrix-Vector Multiplication
We often need to multiply the encrypted vector by a plaintext matrix (e.g., for the CoeffToSlot operation). Since we cannot access rows/columns directly, we use the **Diagonal Method**. This opertion allows to perform linear transformation homomorphically on slots. For example:
- We have a matrix $A$, and $z=[1,2,3,4]$ encrpyted as $ct(X)$, The goal is to have a new ciphertext encrpyting $A\cdot z=[30, 70, 110, 150]$.
$$A = \begin{bmatrix}
1 & 2 & 3 & 4 \\
5 & 6 & 7 & 8 \\
9 & 10 & 11 & 12 \\
13 & 14 & 15 & 16
\end{bmatrix}$$
- After applying Homomorphic Matrix-Vector Multiplication, we have $ct_{new}(X)$ encrypting $[30, 70, 110, 150]$.

## 9. Bootstrapping
CKKS is a "leveled" scheme, since the multiplications comsume levels, and the moduli chain will eventually run out of modulus $(q_0\cdot q_1\cdots q_L \rightarrow q_0)$. Bootstrapping refreshes the ciphertext by restoring the moduli chain $(q_0\rightarrow q_0\cdot q_1\cdots q_L)$ to allow infinite computation.

## 10. Conclusion

CKKS (also known as HEAAN) is a homomorphic encryption scheme tailored for approximate arithmetic over real or complex numbers. Its encoding mechanism enables SIMD-style parallelism, and the approximate computation model makes it particularly suitable for privacy-preserving machine learning tasks, such as federated learning. Typical parameterizations use a modulus chain consisting of roughly 30 to 45 primes. When implemented with a residue number system, ciphertext operations can be executed with substantial efficiency gains.
Despite its strong theoretical foundation, the CKKS ecosystem remains undervalued, with most advancements still confined to the academic domain. For further details, refer to the resources linked below.
- [HEAAN CryptoLab](https://www.cryptolab.co.kr/en/products-en/heaan-ai/)
- [OpenFHE](https://openfhe.org/)
- [CKKS.org](https://ckks.org/software/)
- ...more