Homomorphic encryption has been around for a while (in fact it has been debated for around 30 years), but most systems that are Homomorphic are only partially homomorphic thus limiting their use in enabling real world distributed, including cloud based, systems.
I’ll start by briefly describing what the term homomorphic means when used to describe a cryptosystem. If a mathematical operation can be performed on the encrypted data to produce an encrypted output that when decrypted gives the same result as if the operation had been performed on the plaintext.
I’m sure you can see how this removes one of the main barriers to the adoption of cloud computing. If an efficient, proven and thoroughly tested homomorphic encryption system would potentially revolutionise the view of cloud computing security. Currently it is easy to send data to and from the cloud in a secure encrypted manner, however if any computation is to be carried out in this data it has to be unencrypted at some point. When the data is unencrypted in the cloud the risk that employees of the cloud provider, and potentially other customers, could access the data becomes a real concern. It is this risk that is one of the key road blocks to companies moving their data to the cloud.
Additionally some legal / regulatory rules prevent certain unencrypted data types, such as personally identifiable information (PII), leaving countries / regions such as the EU. A system that enabled data to remain encrypted would potentially get around these regulatory issues and allow data to be housed in the cloud (many cloud providers have data centres located in various global locations and can’t guarantee where data will reside. In fact this is one of the benefits of the cloud – the high level of redundancy and resilience provided by multiple data centres in geographically diverse locations).
Some existing algorithms are partially homomorphic, this means that they are homomorphic with regards to one or maybe a couple of operations. For example the RSA algorithm is homomorphic with regards to multiplication.
IBM has published some research in this area in 2009 they proposed fully homomorphic systems that are linked to from here;
Currently fully homomorphic systems are too new and not yet practical enough to be implemented for production systems. For any cryptographic algorithm to be recommended it requires considerably more time to be peer reviewed and tested by security and encryption researchers to allow a reasonable level of assurance that there are not attacks that could be used to unencrypt the data. In terms of practicality currently proposed homomorphic encryption systems, the complexity of the system grows enormously as the number of actions you need to perform on the encrypted data increases. This leads to a massive increase in the computational power required to run the system, this is a non-trivial increase that will not be solved by Moore’s law anytime in the near future.
So homomorphic encryption has now been proven to be possible which is a huge step forwards, and the work done by people like Craig Gentry and the guys at IBM and MIT must be hugely applauded.
Microsoft researchers published a paper in May of this year (2011) titled ‘Can Homomorphic Encyption be Practical’ that can be found here;
This provides an overview of a proposed partially homomorphic implementation along with thoughts on how it could be made fully homomorphic and how the efficiency could be improved. The page also contains some useful links to cloud and lattice based cryptography.
However the reality is that we need several more years for a broader range of cryptographers to examine the cryptosystem to be assured it is secure, and for further work to go into making the system much more efficient.
These are definitely interesting times, and over the next few years I would hope to see homomorphic cryptosystems removing some of today’s key barriers to the adoption of cloud computing services!