The idea of an homomorphic encryption scheme is not a new one.

Already one year after the introduction of RSA (the first public key encryption scheme discovered by the scientific community) it was noticed that RSA had the special property that if you multiply two ciphertexts together, then the resulting value would be a valid encryption of the *product of the original plaintexts! *In other words, by manipulating the ciphertexts (the random looking strings containing your data) you are manipulating *in a meaningful* way the content of the encryptions.

**A “fully” homomorphic encryption scheme**

As said, even RSA allows the user to perform multiplication *directly in the encrypted domain. *Other cryptosystems allow to perform additions in the encrypted domains. But for more than 30 years, we did not know how to construct a scheme that allows users to compute *any function* of encrypted values. That’s why Gentry’s breakthrough in 2009 has generated so much noise, even outside of the scientific community (e.g., Forbes, Business Week, Forbes again).

Among other things, a **fully homomorphic encryption (FHE)** scheme allows to perform **non-interactive secure computation**, and in many applications this is crucial. The classic example is cloud computing: if you don’t trust your cloud provider with your data, you are in trouble: either you have to give away your private data *in clear* (running the risk that the cloud provider looks into possibly confidential data), or you have to encrypt the data before uploading it (losing the advantages of having the cloud computing for you). Another example is **encrypted a spam filter**: you like that your mailbox is not filled with junk, but you might not be happy about Google/Microsoft/etc. reading the contents of all your emails.

But if you encrypt your data with an FHE scheme, *the cloud can compute on your data without looking at it!*

**Wow! When can I start using FHE?**

The first scheme proposed by Gentry was *insanely* inefficient, and many did not believe we would see a working implementation of an FHE scheme for a long time. Fortunately, there are a lot of smart cryptographers around and in the last 4 years the efficiency of FHE schemes has been improved by several orders of magnitude.

To be concrete, in 2010 the available FHE schemes were so inefficient that they would simply not run on any hardware. At Crypto 2012 Gentry Halevi and Smart showed that it “only” takes 36 hours to evaluate AES in the encrypted domain. After one year this can already be done in under 3 hours! (If interaction is not a problem for your application, you could perform the same task using garbled circuits/oblivious transfer/etc. in a few seconds instead.)

**HELib**

The last result was obtained using a new library, recently released under GPL license by Shai Halevi and Victor Shoup. From the author announcement:

At long last, Victor Shoup and myself finally open-sourced (under GPL)

the HE library that we have been working on for the last year and

something. I created a project for this library on github, seehttps://github.com/shaih/HElib

At this point, the documentation of this library is rather thin. You can

find a design-document under the doc sub-directory, and most modules

include fairly extensive comments in the source code itself, but that’s

pretty much it.[…]

To get an idea for the performance of this library, I attach a short

excerpt from a presentation that I gave a few months ago. We should

probably be some 25% faster now than we were back then, but this gives

the right ballpark estimate.We would very much appreciate comments, and would be even happier

if any of you wants to join us in developing this library.— Victor & Shai

There is still a long way before you can start using FHE for your everyday problem, but these improvements are amazing and we should be grateful to Shai and Victor for making their work public.

**Links**

- MPC Lounge Entry for HELib
- Slides by Shai Halevi with (somewhat old) HELib benchmarking.