Craig Gentry has solved a decades-old puzzle, and the implications for cloud computing are enormous, according to fellow researchers.
Gentry's breakthrough, termed fully homomorphic encryption, will allow complex mathematical operations to be performed on encrypted data without ever having to decrypt it or compromise the encryption. The catch is that the technique requires vast amounts of computational power -- up to a trillion times what is sometimes currently used.
Should his work prove out, a defense contractor or a medical research facility, for instance, could send out confidential data to be analyzed without fear of compromising security or regulatory compliance. That could make companies and agencies that now refuse to let such data off their servers more comfortable outsourcing high-value work.
"This is one of the biggest theoretical developments in cryptography in decades," said Scott Aaronson, assistant professor of electrical engineering and computer science at Massachusetts Institute of Technology.
Computation without decryption
"Right now, the system is kind of inefficient. There's a lot of theoretical work yet to do," said Gentry, a doctoral candidate in computer science at Stanford University. Since his system enables addition and multiplication operations on encrypted data, the amount of computation needed increases many orders of magnitude, he said. Gentry made the breakthrough at a summer research program at IBM.
Gentry's work uses public key encryption – the RSA Security algorithm is the de facto standard for electronic communications – with a mathematical model called an "ideal lattice" and a method of error correction that makes it possible to perform basic analytics tasks on the data without ever seeing the data or the results unencrypted.
Since the original RSA algorithm was published in 1978, the problem of how to perform computational work on encrypted data without crippling the security of encryption has remained unsolved. (And see this brief layman's description of Gentry's scheme, posted to a cryptography mailing list.)
Aaronson explains that homomorphic encryption schemes allow calculations to be performed without decryption, since the data is the same shape (homomorphic) in both forms, so operations performed are equivalent. But adding complexity to the kind of operations you can do critically weakens the system, because it allows more information to be discovered about the encrypted data.
"As you introduce more mathematical structure you make your system easier to crack," Aaronson explained.
There could be many practical applications. "You can offload the computational work to someone you don't trust" and get back results, fully encrypted, without ever disclosing the sensitive data.
But that flexibility comes at a price: Gentry's use of lattice modeling brought the solution within reach, but at the price of "a very, very large blow-up in message size . . . 1 bit becomes 1 million bits," Aaronson said.
He added that plenty of theoretical work remained before this kind of encryption could see practical use. "One of the big tasks is to find more efficient variations," he said, adding that a breakthrough of this magnitude was guaranteed to attract a lot of reciprocal research.
Gentry is reasonably confident that his system can become more efficient and said that the ever growing pool of available computing power puts practical application in the not-too-distant future, five or more years away and noted that interest is high. "I've had people contact me and say they're interested in trying to implement [fully homomorphic encryption] right away."