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.…
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.…
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:
@HomomorphicEnc was started by @KristinLauter
and her colleagues with a goal to standardize FHE. 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.

• • •

Missing some Tweet in this thread? You can try to force a refresh

Keep Current with Sergey Gorbunov

Sergey Gorbunov Profile picture

Stay in touch and get notified when new unrolls are available from this author!

Read all threads

This Thread may be Removed Anytime!


Twitter may remove this content at anytime! Save it as PDF for later use!

Try unrolling a thread yourself!

how to unroll video
  1. Follow @ThreadReaderApp to mention us!

  2. From a Twitter thread mention us with a keyword "unroll"
@threadreaderapp unroll

Practice here first or read more on our help page!

Did Thread Reader help you today?

Support us! We are indie developers!

This site is made by just two indie developers on a laptop doing marketing, support and development! Read more about the story.

Become a Premium Member ($3/month or $30/year) and get exclusive features!

Become Premium

Too expensive? Make a small donation by buying us coffee ($5) or help with server cost ($10)

Donate via Paypal Become our Patreon

Thank you for your support!

Follow Us on Twitter!