IBM's homomorphic encryption could revolutionize security

IBM gets a patent on an encryption method that could make it possible to run fully encrypted programs or VMs without first decrypting them

IBM has been granted a patent on an encryption method that, if implemented, could be revolutionary. It makes it possible to process encrypted data without having to decrypt that data first.

Known as "fully homomorphic encryption," this encryption method has long been something of a Holy Grail for computer scientists, and IBM in particular has been seeking this particular prize for years. The company's receipt of a patent is a strong hint it may be inching toward to a practical solution, rather than simply something that works on paper.

The idea behind homomorphic encryption (HE) is simple enough. With most encryption schemes, the encrypted data has to be decrypted entirely before any significant work -- e.g., math or programming operations -- can be done on it. HE, on the other hand, lets you perform math directly on the encrypted data and have the results of that math show in the underlying data.

What's more, all this is done without having to decrypt any of the data and thus expose it to attack. In theory, it means programs -- or whole VMs -- could run while encrypted and exchange encrypted data between them as they did so.

Paul Ducklin of the Sophos "Naked Security" blog put it this way, using a search engine query as an example: "Imagine...if I could simply take your [already] encrypted search terms, leave them encrypted, search for them directly in the still-encrypted database, and get the same results [as a plaintext search]."

The core concept isn't new, as Bruce Schneier pointed out back in 2009 when IBM researcher Craig Gentry first published details about his work with HE schemes. "Visions of a fully homomorphic cryptosystem have been dancing in cryptographers' heads for thirty years," Schneier wrote.

But Schneier was also deeply skeptical about HE being employed in a practical way, IBM breakthrough or no.

Schneier pointed out, "Gentry estimates that performing a Google search with encrypted keywords -- a perfectly reasonable simple application of this algorithm -- would increase the amount of computing time by about a trillion. Moore's law calculates that it would be 40 years before that homomorphic search would be as efficient as a search today, and I think he's being optimistic with even this most simple of examples."

Flash-forward to 2013, when two more folks at IBM, Victor Shoup and Shai Halevi of the IBM T. J. Watson Research Center, claim to have taken Gentry's original breakthroughs and implemented them in a far more practical way. They've since released an open source, GPL-licensed C++ library to perform HE, although the notes for the program indicate it is extremely low-level, "mostly meant for researchers working on HE and its uses."

"Hopefully in time we will be able to provide higher-level routines," writes Halevi.

Skepticism about the most recent set of breakthroughs remains strong, however. Bob Gourley of writes, "I have seen nothing in any of the research that makes me think a solution can be put in place that cannot be defeated by bad guys. And if that can’t be done then the solution will not solve any problems, it will just add processing overhead."

In other words, the biggest problems may not lie with HE itself, but rather with how well it's implemented -- a common weakness with encryption technology in general.

In the meantime, IBM isn't sitting still. in addition to the above-mentioned HE library, IBM is offering public challenges for its HE schemes, so that any successful attacks on the Gentry-Halevi implementation of HE can be examined in detail.

This story, "IBM's homomorphic encryption could revolutionize security," was originally published at Get the first word on what the important tech news really means with the InfoWorld Tech Watch blog. For the latest developments in business technology news, follow on Twitter.

Copyright © 2014 IDG Communications, Inc.