The US military research agency has awarded almost $5 million to speed the performance of an algorithm that could make cloud computing secure.

Homomorphic encryption is currently thought to be a highly desirable form of encryption. The idea is that you can perform operations on the data without having to decrypt it. For example, you could encrypt the data [1,2] to get say {30,87}. You could then perform the operation of adding the two values together and storing the result, i.e. {117}, back in the encrypted file . The almost magic bit is that when you decrypt the file the result is [3], i.e. what you would have got if you had performed the operation on the original unencrypted data. It's a lot like being able to work with objects while they are still inside a locked bag.

Why would you want homomorphic encryption?

The simple and most pressing answer is that you could use it to store your data securely in the cloud and allow cloud based computers to process it without fear of the data leaking out. Other ideas are secure voting systems that can sum the votes without have access to them or knowing the final result and search engines that can find results without having access to decrypted data.

Two years ago IBM researcher Craig Gentry worked out how to perform the magic that is homomorphic encryption. See: Modifiable encryption for a fuller account of how the method works. The only problem is that his scheme took too long to implement. Put simply the encryption was so inefficient that it made cloud manipulation of the data impractical. Even though the method wasn't practical Gentry has recently been given the 2010 ACM Grace Hopper award for his initial work on homomorphic encryption.

Now the Defense Advanced Research Projects Agency (DARPA), an agency of the United States Department of Defense responsible for the development of new technology for use by the military, has awarded $4.9 million to esearch contractor, Galois Inc, to turn the algorithm into something practical. This is part of a larger project funded to the tune of $20 million called Programming Computation on Encrypted Data or PROCEED (presumably the term homomorphic is too technical).The goal of the project is to speed up the algorithm by a factor of 10 million - which is clearly not an easy optimisation factor to achieve.

As if to demonstrate that interest in homomorphic encryption really is hotting up, DARPA's intelligence counterpart, IARPA, has released a call for proposals for a similar project. In this case the aim is specifically to use homomorphic encryption in database queries, message queues and outsourced data storage systems.

Why exactly DARPA and IARPA need to get involved in the problem is an interesting question - is there an additional military angle that isn't obvious?

If you think that $20 million is a lot just for an algorithm consider the reason why it is difficult. An encryption system has to "mix up" the data in a complex way that makes it difficult to un-mix unless you have another piece of information - i.e. the key. This mixing up can't leave any obvious structure or regularity that the data had visible to the outside world because this could be used to perform unmixing without the key.

Homomorphic operations however need there to be some of the original data's structure left in the mix so that they can work and give a sensible result when the whole lot is unmixed again. When you think about it this way it almost seems that there should be a law which says "any sufficiently strong encryption system cannot be a homomorphic encryption system" - but apparently there isn't.

More Infomation

Craig Gentry thesis: A Fully homomorphic Encryption Scheme

News item on the original discovery: Modifiable encryption 

Galois press release

<ASIN:0387779930>

<ASIN:3540492437>

<ASIN:0883857197>

<ASIN:0471597562>

<ASIN:1584885513>

<ASIN:0201616475>