---
# System prepended metadata

title: VIII. Homomorphic Additive and Multiplicative Ciphertexts

---

# 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.