Homomorphic Encryption in the Real World
For those following developments in cryptography, homomorphic encryption has been a hot topic in the last few years. Well, most practitioners are only interested in cryptography for what it can provide: data encryption, secure networking protocol, authentication and the ever controversial Digital Rights Management. It turns out that homomorphic encryption (HE) holds a big practical promise: when HE is finally available with good performance, people will be able to farm out CPU-intensive loads to the cloud, without having to share their actual data with the servers that process the data. So, when that happy day comes, we’ll be able to benefit from the infinite scalability of the cloud, without paying the price in security.
To give a completely made up example, suppose I had wanted to calculate the sum of a few numbers (3, 4, and 9), but did not want to expend my own resources on this heavy computation. Instead, I would like a cloud service to do it for me. I could multiply each one of them by a secret value (say, 7), send them over to the cloud to be summed up, and when I get the answer back (112, in case you were wondering), “decode” the response – divide by 7 – to get the answer to my original query, which happens to be 16.
In reality of course, I would like the cloud computer to perform much more complicated computations for me. One common example is video transcoding. Can I send a video to the cloud to have it converted from HD to something that’ll fit on my smartphone, without the cloud service getting to know my video preferences? The answer today is an emphatic No.
The Cryptography Research group at IBM has been instrumental in proving that fully homomorphic encryption (FHE) is possible; that is, a cloud service can be built to implement any arbitrary function over encrypted data. Since then, they have been continuously optimizing their implementation. However efficient FHE is still not here. As one data point, a single AES block encryption (a few nanoseconds on your favorite desktop), will take something like 24 hours (!) using FHE techniques.
So while fully homomorphic encryption is not yet possible, we are starting to see examples of practical partially homomorphic solutions. These are solutions that use cryptographic functions that allow the cloud service to evaluate some functions of the input, but not others. For example, it may be able to compute an average of the given inputs, but not their product. While obviously much more limited than FHE, there are already some good applications of “partial homomorphic encryption”. Here are a few:
- CryptDB is a database privacy layer that adaptively encrypts some of the data, so as to minimize the amount of plaintext data available on the database server, while maintaining the ability of the server to perform useful operations (e.g. the SQL “select” and “join” commands) on the data. This project has been developed by a research group at MIT, led by Raluca Ada Popa.
- The Microsoft Cryptography Research Group led by Kristin Lauter has been working on different uses of HE for the last few years. This includes a Healthcare Privacy project with the notion of Patient Controlled Encryption, where patients encrypt their medical data with their private keys, while still retaining the ability of medical organizations to search their records for telltale statistical indicators. This was later extended into novel machine learning algorithms that manage to extract trends and correlations from collections of encrypted patient data sets.
- Porticor is using partially homomorphic encryption as part of its cloud key management protocol. This is actually the first commercial implementation of HE.
To summarize, homomorphic encryption promises to one day allow large scale cloud computations on encrypted data. While several research labs are busily working to bring that day closer, there are already a few implementations that utilize partially homomorphic (or “somewhat homomorphic”) encryption to achieve many of the benefits, using technology available today.
About the Author
Gilad Parann-Nissany is the founder and CEO of Porticor Cloud Security. He is a pioneer in the field of cloud computing who has built SaaS clouds, contributed to SAP products and created a cloud operating system.
Gilad has written extensively on the importance of cloud encryption and encryption key management for PCI and HIPAA compliance.