Fully Homomorphic Encryption (FHE) is a groundbreaking cryptographic innovation that enables computation on encrypted data without needing to decrypt it. This capability preserves privacy throughout the data lifecycle, especially in untrusted environments like cloud servers or collaborative computations. In this article, we explore the core ideas based on Zvika Brakerski’s influential survey, Fundamentals of Fully Homomorphic Encryption, highlighting its origins, definitions, key properties, and practical implications.
Origins of Fully Homomorphic Encryption
The concept of performing computation on encrypted data traces back to the late 1970s. While early schemes such as RSA and ElGamal exhibited partial homomorphic properties (supporting multiplication or addition), a comprehensive scheme that supported both remained elusive.
The field took a significant leap forward in 2009, when Craig Gentry introduced the first FHE scheme. His construction demonstrated that arbitrary computations could be executed over encrypted inputs by applying both addition and multiplication in an encrypted form. However, Gentry’s solution was computationally intensive due to a key operation called bootstrapping, which refreshes ciphertexts to manage noise growth.
Brakerski’s subsequent work, including the BFV and BGV schemes, streamlined these computations, reduced complexity, and contributed to making FHE more practical.
Definition of Fully Homomorphic Encryption
A Fully Homomorphic Encryption scheme includes the following components:
- KeyGen: Generates a secret key and a public key based on a security parameter.
- Enc: Encrypts a message using the public key.
- Dec: Decrypts the ciphertext using the secret key to recover the original message.
- Eval: Takes a function and a set of ciphertexts and returns a new ciphertext that encrypts the function’s output on the original plaintexts.
Formally, for messages m1,m2m_1, m_2m1,m2 and function fff, an FHE scheme ensures: Dec(Eval(f,Enc(m1),Enc(m2)))=f(m1,m2)\text{Dec}(\text{Eval}(f, \text{Enc}(m_1), \text{Enc}(m_2))) = f(m_1, m_2)Dec(Eval(f,Enc(m1),Enc(m2)))=f(m1,m2)
Key Properties of FHE
1. Homomorphism
FHE supports both addition and multiplication operations, enabling evaluation of any computable function by simulating logic gates and circuits.
2. Compactness
The size of the ciphertext produced by the Eval function does not grow excessively with the complexity of the function being evaluated.
3. Bootstrapping
A bootstrapping operation re-encrypts a noisy ciphertext to reduce its noise level, allowing further operations. This makes the scheme fully homomorphic, enabling indefinite computations.
4. Leveled Homomorphism
A subset of FHE, known as leveled homomorphic encryption, supports computations up to a pre-determined circuit depth without bootstrapping. It is more efficient and often sufficient for practical use cases.
Constructions and Techniques
Modern FHE schemes typically rely on lattice-based cryptography, which is believed to be secure even against quantum adversaries. Common constructions include:
- BFV (Brakerski-Fan-Vercauteren): Efficient arithmetic over integers.
- BGV (Brakerski-Gentry-Vaikuntanathan): Offers modular and flexible parameter tuning.
- CKKS: Supports approximate arithmetic for real-number computations, ideal for encrypted machine learning tasks.
All of these schemes use ring learning with errors (RLWE) as their hardness assumption, which underpins their security and efficiency.
Use Cases of Fully Homomorphic Encryption
FHE unlocks new possibilities in secure and privacy-respecting computation:
- Secure cloud computing: Perform operations on encrypted datasets without exposing sensitive data.
- Privacy-preserving machine learning: Train models or make predictions without revealing training or input data.
- Encrypted search: Search and filter encrypted records securely.
- Regulatory compliance: Process sensitive data without violating data protection laws like GDPR or HIPAA.
Security Considerations
FHE schemes are designed to resist IND-CPA attacks (indistinguishability under chosen plaintext attack). Given their reliance on lattice problems, they are considered post-quantum secure, making them viable even in future cryptographic landscapes dominated by quantum computing.
Final Thoughts
Fully Homomorphic Encryption is more than a theoretical breakthrough—it is becoming a practical tool in the cybersecurity arsenal. While performance and efficiency continue to be areas of active research, the progress made since Gentry’s 2009 scheme is substantial. Thanks to contributors like Zvika Brakerski, FHE is now more accessible and relevant for real-world applications.
We love to share our knowledge on current technologies. Our motto is ‘Do our best so that we can’t blame ourselves for anything“.