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.

This story is part of our May/June 2010 Issue
See the rest of the issue
Subscribe

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.

Tech Obsessive?
Become an Insider to get the story behind the story — and before anyone else.
Subscribe today

Uh oh–you've read all five of your free articles for this month.

Insider Premium

$179.95/yr US PRICE

More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe and become an Insider.

  • Insider Premium {! insider.prices.premium !}*

    {! insider.display.menuOptionsLabel !}

    Our award winning magazine, unlimited access to our story archive, special discounts to MIT Technology Review Events, and exclusive content.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

    First Look. Exclusive early access to stories.

    Insider Conversations. Join in and ask questions as our editors talk to innovators from around the world.

  • Insider Plus {! insider.prices.plus !}* Best Value

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus ad-free web experience, select discounts to partner offerings and MIT Technology Review events

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

    Access to the Magazine archive. Over 24,000 articles going back to 1899 at your fingertips.

    Special Discounts to select partner offerings

    Discount to MIT Technology Review events

    Ad-free web experience

  • Insider Basic {! insider.prices.basic !}*

    {! insider.display.menuOptionsLabel !}

    Six issues of our award winning magazine and daily delivery of The Download, our newsletter of what’s important in technology and innovation.

    See details+

    What's Included

    Bimonthly home delivery and unlimited 24/7 access to MIT Technology Review’s website.

    The Download. Our daily newsletter of what's important in technology and innovation.

You've read of free articles this month.