# VIII. Homomorphic Additive and Multiplicative Ciphertexts

[TOC]

## Introduction
This is the eighth chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. In this chapter, we show the homomorphic properties of LWE/RLWE ciphertexts and the problems left to solve in order to acheive **fully homomorphism**.

🚪 Recall of Ring LWE: [V. Ring Learning With Error (RLWE)](https://hackmd.io/Q_6T-id7RzmodNUWn_JzPQ)

## Notation
- $N$: The degree of the polynomial quotient ring.
- $\mathcal{R}_Q = \mathbb{Z}_Q[X]/(X^N + 1)$
- $Q$: The modulus of the ciphertext. $Q=\prod^L_{i=0}q_i$, and $\log Q \ge 200$ (very big).
- $\Delta$: The scaling factor (e.g., $2^{40}$), used to preserve precision when rounding to integers.
- For example, let $\Delta=4$, we have $1.23456\times \Delta \times \frac{1}{\Delta}=1.2345$)

## Definition of Homomoprhism
- A function $f$ is a homomorphism if performing the operation gives the same result, whether you do it before or after mapping (use $\circ$ for the first set and $\bullet$ for the second set):
**$$f(a \circ b) = f(a) \bullet f(b)$$**
- 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)$$**
- 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)$$**

## Homomorphic Addition

Homomorphic addition is computationally inexpensive. It involves simple component-wise addition of the polynomials in the ring $\mathcal{R}_Q$.

### Addition of Ciphertext & Plaintext
- **Input:**
- Ciphertext $c = (a, b)$ encrypting $m$, and
- A plaintext polynomial $m' \in \mathcal{R}_Q$ to be added.
- **Operation:**
- Add a plaintext message $m'$ to an encrypted ciphertext.
$$c' = (a, b + \Delta \cdot m')$$
- **Result:**
$$b + \Delta \cdot m' + a \cdot s = (\Delta \cdot m + e) + \Delta \cdot m' = \Delta \cdot (m + m') + e$$
- **Observation:**
- The noise $e$ remains effectively unchanged, so the decryption works fine and returns $m + m'$.

### Addition of Ciphertext & Ciphertext

- **Input:**
- $c_1 = (a_1, b_1)$ encrypting $m_1$
- $c_2 = (a_2, b_2)$ encrypting $m_2$.
- **Operation:**
- This operation adds two encrypted messages.
$$c' = (a_1 + a_2, b_1 + b_2) \pmod Q$$
- **Result:**
$$(b_1 + b_2) + (a_1 + a_2) \cdot s = \Delta \cdot (m_1 + m_2) + (e_1 + e_2)$$
- **Observation:**
- The noise grows additively: $e' = e_1 + e_2$. As long as the accumulated error doesn't exceed $\frac{\Delta}{2}$, the decryption still works correctly. The growth of error is under control.

## Homomorphic Multiplication

Multiplication is significantly more expensive than addition. It increases the noise multiplicatively and expands the ciphertext size, requiring auxiliary operations to manage.

### Multiplication of Ciphertext & Plaintext
- **Input:**
- Ciphertext $c = (a, b)$ encrypting $m$
- A plaintext $m' \in \mathcal{R}_Q$ or a scaler $\alpha\in \mathbb{Z}_Q$
- **Operation:**
- Multiply a plaintext message $m'$ to an encrypted ciphertext.
- The operation that multiplies $\alpha$ is ignored here, since they are simply the same.
$$c' = (a \cdot m', b \cdot m') \pmod Q$$
- **Result:**
\begin{align}
(b \cdot m') + (a \cdot m') \cdot s &= m' \cdot (b + a \cdot s) \\
&= m' \cdot (\Delta \cdot m + e) \\
&=\Delta \cdot (m \cdot m') + m' \cdot e
\end{align}
- **Observation:**
- The noise grows with the size of m: $e' = m' + e$. As long as the accumulated error doesn't exceed $\frac{\Delta}{2}$, the decryption still works correctly. However, the growth of error is faster compared to homomorphic addition, we apply **decompistion method** to reduce the growth of error.

### Multiplication of Ciphertext & Ciphertext
- **Input:**
- $c_1 = (a_1, b_1)$ encrpyting $m_1$
- $c_2 = (a_2, b_2)$ encrpyting $m_2$
- **Operation:**
- 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}_{\text{New Noise Term}}
$$
We treat $\Delta m_1e_1$ , $\Delta m_2e_2$, and $e_1e_2$ to be a new noise term $e_{mult}$
- Expanding the left hand side:
$$
(b_1 + a_1 s) \cdot (b_2 + a_2 s)
=\underbrace{b_1 b_2}_{\text{Degree } 0} + \underbrace{(a_1 b_2 + a_2 b_1)}_{\text{Degree } 1} \cdot s + \underbrace{(a_1 a_2)}_{\text{Degree } 2} \cdot s^2
$$
- Assign the cross-terms:
- $d_0 = b_1 b_2$
- $d_1 = a_1 b_2 + a_2 b_1$
- $d_2 = a_1 a_2$
- These terms correspond to the decryption equation squared:
$$
(b_1 + a_1 s)(b_2 + a_2 s) = d_0 + d_1 s + d_2 s^2
$$
- Observe that $d_0+d_1s$ is valid RLWE-based ciphertext form $c_0=(d_0, d_1)$. If we transform $d_2s^2$ into a valid ciphertext form $c_1=(d_3, d_4)$ such that $d_2 s^2\approx d_3+d_4s$, then we can do homomorphic addition: $c_2=c_0+c_1$ and decrypt $c_2$ to get $\Delta^2m_1m_2+e_{mult}$. The process is called **relinearization**.
- **Relinearization by Key Switching:**
- If we treat $s^2$ as a secret key, the relinearization is to switch a key: $s^2$ to $s$. With a a specialized evaluation key $evk$, we have $d_2 s^2\approx d_3+d_4s$, and $c_1=\text{KeySwitch}(d_2, evk)=(d_3, d_4)$
- Apply homomocphic addtion of $(d_0, d_1)$ and $(d_4, d_4)$, we have
$$c_2 \leftarrow (d_0, d_1) + \text{KeySwitch}(d_2, evk)=(d_0+d_3, d_1+d_4)$$
The result is the addition of two ciphertexts $c_0$ and $c_1$, encrypting $\Delta^2 \cdot m_1 m_2$ with error $e_{mult}$.
(We explain how a evaluation key is constructed in next chapter.)
- **Issue Observations:**
- **Quadratic Secret $d_2s^2$**: To get a valid ciphertext form in order to do ciphtext to ciphtext addtion, we have to do relinearization for $d_2s^2$. This process also introduces some new error.
- **Scale Squared:** Every multiplication squares $\Delta \rightarrow \Delta^2$. If left unchecked, the message magnitude grows exponentially, quickly overflowing the modulus $Q$. Thus, scaling down the squared scaling factor is needed.
- **Noise Explosion:** The error term is no longer just $e$. It now includes $\Delta \cdot m \cdot e$. Since $\Delta$ is large (e.g., $2^{40}$), the error has grown significantly.