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.

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.

DGHV

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.

BGV

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.

BFV

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.

FHEW

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.

CKKS

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.

TFHE

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.