A novel technique could see future Web services work with sensitive data without ever being able to read it. Several implementations of a mathematical proof unveiled just last year will allow cryptographers to start making the proposal more practical.

In 2009 Craig Gentry of IBM published a cryptographic proof that was that rare thing: a true breakthrough. He showed that it was possible to add and multiply encrypted data to produce a result that--when decrypted--reveals the result of performing the same operations on the original, unencrypted data. It's like being able to answer a question without knowing what the question is.

Called "fully homomorphic encryption," it has been dubbed the holy grail of cryptography. Addition and multiplication are the building blocks of computation, and being able to compute data without decrypting it would allow new levels of security. For example, someone could send an encrypted database of medical records to a cloud computing provider, secure in the knowledge that they could use the service to work on the data as usual without ever decrypting it. The results of a search could be sent to the data's owner, who could decode it on his own system. The same approach could secure webmail or online office suites.

Nigel Smart, professor of cryptology at Bristol University, in the U.K., and collaborator Frederik Vercauteren, a researcher at Katholieke Universiteit Leuven, in Belgium, have now reworked the original proposal into a version that can be implemented and tested. "We've taken Gentry's scheme and we made it simpler," says Smart. While Gentry's original scheme encoded everything in matrices and vectors, Smart and Vercauteren instead use integers and polynomials. "That makes it both easier to understand, and to work with," says Smart, "you can actually compute with it and do real calculations."

The original scheme's reliance on large matrices and vectors made it impractical because of the complexity of working with every element of the matrices at each step, and the fact that their complexity grows significantly with each extra operation on the data. Smart and Vercauteren's rewrite of the scheme sidesteps that enough to allow testing of actual implementations of Gentry's idea on a desktop computer. "We do implement it, and we can actually encrypt bits and add and multiply a little bit," says Smart. "We can do about thirty sequential operations."

The usefulness of the scheme is still limited by the fact that, as more operations are performed, successive encrypted answers degrade, becoming "dirty," as Smart puts it. That means the current version isn't truly fully homomorphic, since it can't perform any arbitrary calculation.