Homomorphic encryption (HE) has evolved from a theoretical curiosity into a cornerstone of modern privacy-preserving computation. Its development spans over four decades, marked by major breakthroughs in cryptography that have gradually turned the idea of computing on encrypted data into a practical reality. This article outlines the key milestones in the history of homomorphic encryption, illustrating its journey from early conceptualization to the advanced schemes used today.
1978: The Foundation – Multiplicative Homomorphism in RSA
The concept of homomorphic encryption was first observed in 1978, shortly after the invention of the RSA algorithm. Researchers noted that RSA exhibited multiplicative homomorphism — meaning that the product of two ciphertexts decrypted equals the product of the original plaintexts: Enc(x)⋅Enc(y)=Enc(x⋅y)Enc(x) \cdot Enc(y) = Enc(x \cdot y)Enc(x)⋅Enc(y)=Enc(x⋅y)
This marked the beginning of partially homomorphic encryption (PHE), where only one operation (multiplication, in this case) is supported.
2009: Gentry’s Breakthrough – Fully Homomorphic Encryption
After decades of theoretical speculation, Craig Gentry introduced the first fully homomorphic encryption (FHE) scheme in 2009. This was a game-changer — a system capable of supporting both addition and multiplication, enabling arbitrary computation on encrypted data.
However, Gentry’s scheme was extremely slow — it took approximately 30 minutes to perform a single logical operation on standard hardware. Despite this, it proved that FHE was possible, sparking intense research and development in the field.
2011–2012: Second Generation – Practical Leveled HE
The second generation of HE schemes came shortly after, with notable contributions including:
- BFV (Brakerski/Fan-Vercauteren)
- BGV (Brakerski-Gentry-Vaikuntanathan)
These are leveled homomorphic encryption schemes, meaning they can evaluate circuits of a pre-determined depth without bootstrapping (a costly operation that refreshes ciphertexts). While not truly “fully” homomorphic, they made homomorphic encryption practical for the first time by:
- Eliminating the need for frequent bootstrapping
- Supporting limited, yet useful, computation without revealing data
These schemes are foundational to many modern HE libraries and tools.
2013–Present: Third Generation – Bootstrapping Reimagined
The third generation of FHE schemes reintroduced bootstrapping, but in a smarter way:
- GSW (Gentry-Sahai-Waters) and successors like CGGI brought the concept of programmable bootstrapping, where the bootstrapping step also performs computation.
- This approach reduced noise and simultaneously evaluated functions, making bootstrapping more efficient and meaningful.
These advances pushed FHE closer to real-world applications by improving speed and versatility while maintaining strong security guarantees.
Where Are We Now?
Homomorphic encryption continues to evolve with frameworks like:
- Microsoft SEAL
- IBM HELib
- PALISADE
- TFHE (Fast Gate-by-Gate Evaluation)
These libraries implement the latest FHE techniques and are being integrated into sectors like finance, healthcare, AI, and secure cloud computing.
Security Considerations
All HE schemes aim for IND-CPA security — indistinguishability under chosen plaintext attacks. While this provides a solid foundation, achieving stronger security models like IND-CCA2 remains a challenge due to the complexity of HE schemes.
Conclusion
Homomorphic encryption has transitioned from an abstract cryptographic dream to a near-ready technology poised to revolutionize data privacy. With ongoing improvements in performance, programmability, and security, FHE is set to play a pivotal role in enabling secure, privacy-preserving computation across untrusted environments.
We love to share our knowledge on current technologies. Our motto is ‘Do our best so that we can’t blame ourselves for anything“.