IBM researcher Craig Gentry has proposed a method for manipulating data while leaving it encrypted. That could be big news for cloud computing, for antispam solutions, and for health care providers, according to an IBM (NYSE: IBM) statement — if it works.
The news comes as regulators are monitoring the handling of personal data. The FTC recently announced the Red Flags rule to force companies to fight fraud more actively. Just yesterday, the now-famous ID thief Frank Abagnale, whose life story inspired the movie “Catch Me If You Can” and who now works for the FBI, said that companies must do better to protect their customers.
It’s possible that they can with the breakthrough proposed in a paper by Gentry, a Stanford University Ph.D. candidate. The research was reported last week and published for Association of Computing Machinery members under the title “Fully homomorphic encryption using ideal lattices.”
Homomorphic encryption enables encrypted data to be manipulated so that, when decrypted, the result is as if the operation had been performed on the unencrypted data — an approach that makes it especially suitable for some types of security. Lattice encoding would normally limit the number of operations that could be conducted on the encrypted text, according to PGP Corporation cryptographer Hal Finney, who discussed the approach on a list serv.
But Gentry’s approach manages to overcome those shortcomings.
“The resulting scheme is apparently not practical … but it is still amazing that it is even possible,” Finney wrote.
One problem may have to do with the fact that although the data is not decrypted, the software does manipulate a decryption mechanism while working with encrypted data. The ACM abstract notes that Gentry’s technique uses “an encryption scheme that can evaluate (slightly augmented versions of) its own decryption circuit; we call a scheme that can evaluate its (augmented) decryption circuit bootstrappable.”
Nevertheless, IBM has high hopes for the technology.
“We believe this breakthrough will enable businesses to make more informed decisions, based on more studied analysis, without compromising privacy,” Charles Lickel, IBM vice president of software research, said in a statement. “We also think that the lattice approach holds potential for helping to solve additional cryptography challenges in the future.”
Additionally, an IBM representative told InternetNews.com that “there are flavors of homomorphic encryption already out there, but they do not offer efficient, affordable ways of analyzing encrypted information from all angles. The fully homomorphic solution we’ve arrived at offers the possibility of performing nearly unlimited mathematical operations to analyze encrypted information.”
PGP’s Finney was certainly impressed with Gentry’s technique. “I have to go back to Godel‘s and Turing‘s work to think of a comparable example,” he wrote.
“This is … one of the most remarkable crypto papers ever. Not only does it solve one of the oldest open problems in cryptography, the construction of a fully homomorphic encryption system, it does so by means of a self-embedding technique reminiscent of Godel’s theorem.”