Types of Homomorphic Encryption (FHE, SHE, PHE)
Homomorphic encryption schemes are primarily categorized based on the types and number of operations they can perform on ciphertexts. Understanding these categories is key to appreciating their capabilities and limitations.
1. Partially Homomorphic Encryption (PHE)
PHE schemes allow for only one type of mathematical operation to be performed an unlimited number of times on encrypted data. For example, a PHE scheme might support unlimited additions or multiplications, but not both.
- Operations: Supports either addition or multiplication, but not both.
- Examples:
- RSA: Supports unlimited multiplications on ciphertexts.
- Paillier Cryptosystem: Supports unlimited additions on ciphertexts.
- ElGamal Cryptosystem: Can be set up to be additively or multiplicatively homomorphic.
- Usefulness: PHE schemes are generally more efficient and simpler to implement. They are suitable for applications where only a single operation type is repeatedly needed, such as secure e-voting or statistical computations.
2. Somewhat Homomorphic Encryption (SHE)
SHE schemes can perform a limited number of different types of operations on ciphertexts. The limitation typically arises because noise in the ciphertext increases with each operation. After a certain number of operations, the noise becomes too large, and the resulting ciphertext can no longer be correctly decrypted.
- Operations: Supports a limited set of operations (e.g., some additions and multiplications) up to a certain complexity or depth.
- Limitation: The number of operations is restricted by noise growth. Each operation adds noise to the ciphertext, and eventually, this noise overwhelms the original message.
- Usefulness: SHE is more versatile than PHE as it can handle more complex computations, such as evaluating low-degree polynomials on encrypted data. However, the circuit depth must be known and limited in advance.
3. Fully Homomorphic Encryption (FHE)
FHE is the most powerful and versatile form of homomorphic encryption. FHE schemes allow for an unlimited number of any type of computation to be performed on ciphertexts.
- Operations: Supports arbitrary computations, meaning an unlimited number of both additions and multiplications.
- Key Technique - Bootstrapping: The breakthrough that enabled FHE was the concept of "bootstrapping," introduced by Craig Gentry in 2009. Bootstrapping is a process that "refreshes" a ciphertext by homomorphically evaluating its own decryption circuit, reducing accumulated noise and allowing further computations.
- Usefulness: FHE is the "holy grail" because it can theoretically handle any computation on encrypted data. This opens up vast applications from secure cloud computing to privacy-preserving machine learning.
- Challenges: Current FHE schemes are often computationally intensive with significant performance overhead and large ciphertexts. Research actively focuses on making FHE more practical and efficient.
In Summary
The journey from PHE to FHE represents significant advancement in cryptography. While PHE schemes are efficient for specific tasks and SHE schemes offer more flexibility with limitations, FHE provides the ultimate goal of arbitrary computation on encrypted data. The choice of which type to use depends heavily on specific application requirements, including computation complexity and performance constraints.