# II. History of Homomorphic Encryption

[TOC]

## Introduction
This is the second chapter of [Understanding Homomorphic Encryption](https://hackmd.io/@spockwall/rJgV4qFgZe) series. This chapter we discuss the evolution of HE, tracing the path from early schemes that supported only partial HE to the pivotal breakthroughs that enabled the realization of Fully Homomorphic Encryption. This historical context is essential for appreciating the complexity and significance of modern lattice-based schemes.

## What Is Homomorphism?
In mathematics, a **homomorphism** is a "structure-preserving" map between two algebraic structures.
### Excample
Imagine the operation of **addition** in the set of real numbers (e.g., $x + y$) and the operation of **multiplication** in the set of positive real numbers.

- The **exponential function** $f(x) = e^x$ is a homomorphism *from* addition *to* multiplication.
- It "preserves the structure." If you add two numbers first and then apply the function, you get the same result as applying the function to each number first and then multiplying.
**$$f(x + y) = f(x) \times f(y) = e^x \times e^y = e^{(x+y)}$$**
The structure is preserved: **Addition** in the first world maps to **Multiplication** in the second world.

---

### The Core Principle

- 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)$$**
- This means you can do your work in the "original" world ($a \circ b$) or in the "mapped" world ($f(a) \bullet f(b)$) and get a corresponding result.

---

### Connection to Cryptography
- In this context, the "map" is the **encryption function** ($E$). The "original world" is your plaintext data, and the "mapped world" is the encrypted ciphertext.
- An **additive homomorphic** scheme, (like Paillier) preserves the addition operation. It allows you 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)$$**
- For a fully homomorphic encryption scheme, additive and multiplicative homomorphism are achieved with the construction of encrpytion function.

## Partial Homomorphic Encryption (PHE)
**Partial Homomorphic Encryption (PHE)** refers to cryptosystems that allow for one specific type of mathematical operation (either addition or multiplication) to be performed an unlimited number of times on encrypted data.
This is in contrast to **Fully Homomorphic Encryption (FHE)**, which allows for *both* addition and multiplication. Because PHE systems are limited to a single operation, they are generally much faster and more efficient than FHE, making them practical for specific applications like secure e-voting or statistical analysis.

---

### RSA (1977)
- THe RSA encryption scheme is **multiplicatively homomorphic**.
- **Property:** Multiplying two RSA ciphertexts together results in a new ciphertext that, when decrypted, yields the product of the original plaintexts.
- **How it works:**
* Let $E(m_1) = m_1^e \mod n$ be the ciphertext of message $m_1$.
* Let $E(m_2) = m_2^e \mod n$ be the ciphertext of message $m_2$.
* If you multiply these two ciphertexts:
$E(m_1) \times E(m_2) = (m_1^e \mod n) \times (m_2^e \mod n)$
$= (m_1 \times m_2)^e \mod n$
$= E(m_1 \times m_2)$
- **Key Caveat:** This homomorphic property is **lost in modern, secure implementations of RSA**. Secure RSA requires padding schemes (like OAEP), which add randomness to the message before encryption. This randomness breaks the multiplicative relationship.

---
### Elgamal (1984)
- The **Elgamal** cryptosystem is also naturally **multiplicatively homomorphic**.
- **Property:** Multiplying two Elgamal ciphertexts (specifically, their corresponding components) results in a ciphertext that decrypts to the product of the original plaintexts.
- **How it works:**
* An Elgamal ciphertext for a message $m$ is a pair $(c_1, c_2)$.
* $E(m_1) = (c_{1a}, c_{2a})$
* $E(m_2) = (c_{1b}, c_{2b})$
* Multiplying the components:
$(c_{1a} \times c_{1b}, c_{2a} \times c_{2b}) = E(m_1 \times m_2)$
- **Note:** A variation known as "Exponential Elgamal" can be used to achieve *additive* homomorphism by encoding a message $m$ as $g^m$ (a generator $g$ to the power of $m$) before encryption.

---
### Paillier (1999)
- The **Paillier** cryptosystem is the most widely cited example of an **additively homomorphic** scheme.
- **Property:** Multiplying two Paillier ciphertexts together results in a new ciphertext that, when decrypted, yields the *sum* of the original plaintexts.
- **How it works:**
* Let $E(m_1)$ and $E(m_2)$ be the ciphertexts of messages $m_1$ and $m_2$.
* If you multiply these two ciphertexts:
$E(m_1) \times E(m_2) = E(m_1 + m_2)$
- **Applications:** This property is extremely useful for privacy-preserving applications. For example, in an **e-voting system**, each vote (0 for 'No', 1 for 'Yes') can be encrypted with Paillier. The election server can then multiply all the ciphertexts together. Decrypting this single, combined ciphertext reveals only the *total sum* of the votes, not the individual vote of any participant.

---
### Others
- Additively Homomorphic Schemes
- Benaloh Cryptosystem
- Damgård–Jurik Cryptosystem
- Okamoto–Uchiyama Cryptosystem
- Naccache–Stern Cryptosystem
- Exclusive-OR (XOR) Homomorphic Schemes
- Goldwasser–Micali (GM) Cryptosystem
- Fully-Additive and One-multiplicative Homomorphic Schemes
- **Boneh–Goh–Nissim (BGN) Cryptosystem**: Supports an unlimited number of additions but only one multiplication. It's more powerful than a purely additive scheme. It's often used in situations requiring a single multiplicative step, like calculating a squared distance.

## Somewhat (practical) Homomorphic Encryption (SHE)
- A Somewhat Homomorphic Encryption (SHE) scheme is a system that can perform both addition and multiplication, but only for a limited number of operations.
## Leveled Homomorphic Encryption (LHE)
- A Leveled Homomorphic Encryption scheme is a more powerful and practical version of SHE. It allows you to perform computations up to a pre-determined, bounded depth.
- Note: Both SHE and LHE are a part of building blocks of fully homomorphic encryption schemes.
## Fully Homomorphic Encryption
- **Integer-based FHE: DGHV scheme (2010):**
- The security relies on the **Approximate Greatest Common Divisor (AGCD)** difficulty problem on integers and the lattice difficulty problem.
- **First-Generation FHE: Gentry's scheme (2009):**
- Based on **ideal lattices**.
- The security relies on the **Sparse Subset Summation Problem (SSSP)** assumption.
- Impractical efficiency for implementation.
- **Second-Generation FHE: BGV, (B)FV schemes (2011, 2012):**
- Based on the **(Ring) Learning With Errors (\(R)LWE)) problem**.
- This generation notably no longer relies on the SSSP assumption.
- The message encoding techique makes SIMD available.
- **Third-Generation FHE: GSW, FHEW, TFHE schemes (2013, 2014, 2016):**
- Using bit manipulation, allowing abritrary circuit composition.
- This generation, which uses an approximate eigenvector-based construction, is based on the **\(R)LWE problem**.
- TFHE is based on "Torus" not ring.
- **Fourth-Generation FHE: CKKS scheme (2016):**
- CKKS also called HEAAN is a designed for approximate arithmetic on real or complex numbers. Unlike other schemes that are exact,
- Derived from the second generation, so SIMD is also available.
- Supports approximate arithmetic, is based on the **\(R)LWE problem**.
- There is a exact version of CKKS.

## FHE Evolution Graph

## Reference
- [Progress and Applications of Fully Homomorphic Encryption](https://www.researchgate.net/publication/385062114_Progress_and_Applications_of_Fully_Homomorphic_Encryption)
- [History of FHE: A Timeline](https://fhe.org/history/)
- [Open, Application-Driven FHE for Ethereum](https://ethresear.ch/t/open-application-driven-fhe-for-ethereum/23044)