Thread by @sergey_nog

Almost "everything" you need to know about fully homomorphic encryption and how it can solve (at least some) of our data privacy problems.

The problem was first introduced by Rivest, Adleman, and Dertouzos all the way back in 1978. luca-giuzzi.unibs.it/corsi/Support/…

On a high level, an encryption scheme is homomorphic if one can perform field operations over the encrypted messages, E(a) and E(b), that result in simple base operations over the underlying encrypted values.

For example, "addition" of two encryption values E(a) "+" E(b) results in encryption of addition of the corresponding plaintext E(a+b).

An encryption is fully homomorphic (FHE) if it supports both homomorphic addition & multiplication operations. Since any computation can be expressed as a circuit consisting of a series of additions and multiplications, one, in theory, can then compute any program homomorphically

Until 2009, we only knew of encryptions supporting limited homomorphism -- either additions, or multiplications, or many additions followed by a single multiplication [using pairings].

Craig Gentry, in 2009, came up with the first example of fully homomorphic encryption. This was a huge breakthrough and brought new energy to the field. cs.cmu.edu/~odonnell/hits…

The construction was so brilliant and complex that no one understood it. So, the hunt for easier constructions from well-studied assumptions began.

One of the simplest (but not the most efficient) schemes is from Gentry, Sahai, Waters can be found here: eprint.iacr.org/2013/340.pdf.

@HomomorphicEnc was started by @KristinLauter
and her colleagues with a goal to standardize FHE. homomorphicencryption.org contains great refs wrt security, applications, and FHE software libraries.

Where is FHE today and what challenges do we still need to solve to make it practical?

A) You can solve many specific computations (such as machine learning functions) relatively efficiently using FHE.

B) Performing general computations using FHE is still very expensive.

This is partly due to FHE's strong security guarantees: since NO information about the underlying plaintext should be revealed, by default, you cannot terminate one computation earlier than another [i.e. you cannot do binary searches on uneven trees].

Everything has to run in time proportional to the runtime of the computation on the worst input.

In practice, one needs to express any computation as a collection of basic operations over the ciphertext, which requires building new compilers and software execution stacks.

Finally, how do you even debug a program that runs on data encrypted with FHE? Was the bug due to the program, its FHE equivalent, or the data?

A few side notes: Keep in mind that FHE on its own does not offer any verifiability properties. Naively, there is no way to confirm that the intended computation was done correctly.

However, there are tools and techniques (including zero-knowledge proofs) that one can apply, of course, to address these limitations, subject to increased computational overheads.

Where do we go from here?

FHE was a breakthrough that sparked the interest of many in cryptography. Its applications range from secure cloud and space computing, blockchains, and beyond.

Fundamentally, it enables individuals to obtain privacy while still leveraging remote compute nodes.

As Rivest states, on avg, it takes ~20 years for a crypto primitive to go from theory to practice. We're about 13 years in the making of FHE. While many challenges remain to be addressed, it will inevitably be integrated in the tools we use in our daily lives 5-10 years from now.