History of FHE: A Timeline

Since the 1970s there had been a dream of Fully Homomorphic Encryption, a dream that was questioned as even possible.

Fast forward to 2009, when Craig Gentry described the first feasible construction for a Fully Homomorphic Encryption scheme using lattice-based cryptography. Since then FHE has grown from a research fascination to a sprawling community of schemes, libraries, developers, and increasing public interest in its application.

Here we take a look at where it all started and just how far it's come.

What is FHE?

FHE is the first form of cryptography that enables you to run computations on encrypted data without needing to first decrypt it.

Check out this clip from the very first meetup featuring Pascal Paillier explaining where FHE comes from.



Privacy Homomorphisms

FHE emerged approximately forty years ago within the field of cryptography, initially a concept at the time termed 'privacy homomorphism'. The idea involved an encryption function acting as a homomorphism (e.g. it preserves specific operations like addition or multiplication), but to perform operations on encrypted data (ciphertext) such that these operations, in turn, would have a corresponding effect on the original, unencrypted data (plaintext).


RSA scheme

The RSA cryptosystem, founded in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, was a pivotal cryptographic algorithm that laid foundational concepts for the field of homomorphic encryption. It was the first instance of a partially homomorphic encryption scheme and allowed the multiplication of two ciphertexts to result in an encrypted form of the product of their respective plaintexts.

1978 ~ 2008

Partially Homomorphic Encryption (HE)

Over the next three decades there was a lot of progress as researchers focused on designing encryption schemes that supported homomorphic operations, predominantly addition or multiplication, each modulated by specific constraints. There were no schemes supporting both operations simultaneously though.

The dream within the cryptographic community was to develop an encryption scheme capable of homomorphically supporting both addition and multiplication. This aspiration seemed elusive and many in the field had begun to doubt the feasibility of true homomorphic encryption.


Gentry's Breakthrough

In 2009, a breakthrough occurred. Craig Gentry published the first example of a secure encryption scheme that supported both addition and multiplication homomorphically. This development was unexpected and revolutionary, reigniting interest and opening new avenues in the research of FHE. Gentry's contribution marked a pivotal moment in the evolution of Fully Homomorphic Encryption, transforming it from a theoretical concept into a practical reality.



Directly following, Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathanan built DGHV ("Fully Homomorphic Encryption over the Integers") using only addition and multiplication over the integers (as opposed to more complicated algebraic structures used in e.g. Gentry’s scheme — ideal lattices). This scheme is very simple, conceptually, and is based on the approximate-GCD problem - a different hardness assumption to LWE. Served as a proof that FHE can be built in an easy-to-understand way.



The BGV scheme was introduced by Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan in 2011 based on the hardness of the Ring-Learning with Errors (RLWE) problem. What distinguishes it is its handling of encryption error or "noise," which, like in BFV, increases with homomorphic operations, but BGV is designed to manage this growth, especially after homomorphic multiplications, to maintain security and practicality.



The BFV scheme was introduced in two works by (Barkerski) and (Fan and Vercauteren) in 2012. Brakerski introduced an LWE-based scheme and Fan and Vercauteren ported Brakerski’s scheme to the Ring-LWE setting. One interesting aspect of the BFV scheme was its scale-invariant nature. Unlike in BGV, in BFV the message-bits are encoding into the higher-order-bits of a plaintext.



A boolean FHE scheme was then developed that operates via evaluating boolean gates on encrypted bits. In particular, via an operation which admitted the computation of a homomorphic NAND on two ciphertexts encrypting bits. This was the first recorded instance of bootstrapping in less than a second.



In 2016, the CKKS scheme was introduced by Cheon, Kim, Kim, and Song. This scheme was the first FHE scheme to perform approximate arithmetic over complex, and therefore real, numbers. It used a new encoding technique to map a vector of complex values into a polynomial ring. A new “rescaling” procedure was introduced, allowing for more compact ciphertexts throughout homomorphic evaluation.



Shortly after, a scheme in a similar style as FHEW was developed by Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène that considers a selection of improvements in order to increase efficiency compared to the usage of “Internal Product” in FHEW. Here, the bootstrapping process was considered as a collection of “external products” which increased efficiency. Further techniques outlined how to reduce the bootstrapping key size from ~1GB down to tens of MB. It was the first recorded instance of bootstrapping in less than 100ms.