Intelligent Machines
Computing with Secrets, but Keeping them Safe
A cryptographic method could see cloud services work with sensitive data without ever decrypting it.
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.
Gentry has developed a way to periodically clean the data to enable such a system to self-correct and be fully homomorphic. However, using it requires the system to be capable of a certain number of operations, currently beyond Smart’s implementation. Gentry and his IBM colleague Shai Halevi have been experimenting with their own variant of Smart’s approach, he says, and should announce results of their improvements to it later in the summer.
At the moment, Smart is adjusting the system’s parameters to find out what works best. “For example, generating the keys was very slow; now we can do that better,” he says. “It’s like tuning a racing car; you tweak the engine and discover the tires need adjusting.”
Predicting when that tuning will result in a technique ready for practical use is still impossible, says Smart, “but it will now run, and for people to be actually playing with a completely new method within one year of it first being presented is incredibly fast for cryptography.” By contrast, he points out, a technique known as elliptic curve cryptography that is now used to secure mobile devices like the BlackBerry was first presented in 1985 but not implemented practically until around five years later.
Eleanor Rieffel, a senior research scientist at FX Palo Alto Laboratory, a research center at Fuji Xerox, agrees. “It has progressed fast, but because it’s such a new area nobody really knows what route to take,” she says. “These early implementations will let people experiment and try out ideas.”
Meanwhile, despite the uncertainty over the idea’s future development, interest from the IT world in any progress will remain high, says Rieffel. “There’s more and more interest in being able to store data offsite with another company, or at a different site within a company, so this has a lot of attractions.” It may even be that more powerful, but still limited implementations find use for specific applications, she adds.
