Blog - Cryptomathic

Fully Homomorphic Encryption

Written by Ivan Damgård | 06. February 2012

- hype or the answer to all our prayers?

A couple of years ago, Craig Gentry produced a break-through result in cryptography: what researchers had been dreaming about for more than 25 years was finally possible: Gentry had shown how to do so-called Fully Homomorphic Encryption (FHE). What this allows is for a party A to receive encryptions of a set of inputs to some computation. A does not have the key for decryption and so has no idea what the inputs are. Nevertheless, he can perform ANY computation he wants on the data while they are encrypted, and in the end come up with the desired result in encrypted form. This can then be sent to one or more parties who have access to the decryption key and they will then learn the results in the clear.

This sounds like the ultimate solution for doing cloud computing while preserving privacy of all input data. And indeed it is - at least in principle, and if we conveniently forget about issues such as how we know that the results are correctly computed. However, we are still very far from being able to realize such an application in practice. Current FHE schemes are extremely inefficient and in fact much too slow for any real application. Recent implementations take up to 30 minutes on a powerful 64-bit machine to do a basic operation (see http://eprint.iacr.org/2010/520). Lots of research effort is being spent to do something about this, and it is beyond doubt that we will have more efficient solutions in the future. Whether we will ever be able to use FHE directly for real applications is still an open question, however.

A common misunderstanding is that secure computing on confidential data suddenly became possible when FHE was invented. This is not true at all, we have known how to do this since the late 80's: if several parties are involved in the computation, they can collaborate to do any computation securely: just as when using FHE, the inputs will remain private and only the intended results will be released. These multiparty solutions are very practical indeed, and are already being used for industrial applications (see http://www.springerlink.com/content/j4772m44r05x0527/.) Interestingly, ideas and techniques derived from FHE are now being used to make these solutions even better, for a recent example of this, see http://eprint.iacr.org/2011/535.

To conclude: yes, FHE was an amazing breakthrough in theoretical cryptography and as such it deserves all the attention is has been given. But it is not yet an immediate answer to practical secure computing. Fortunately, however, for this we already have solutions that will become even better when combined with techniques derived from FHE, and such combinations look like the best answer to the actual needs of applications.

Image: "Sicherheit", courtesy of Olli Henze, Flickr (CC BY-ND 2.0)