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.)
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, see
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.