Craig Gentry wins dissertation award
If you’ve signed up for a Web-based e-mail service such as Google’s Gmail, or Yahoo! Mail, then you are a user of “cloud computing,” in which the storage and processing resources that data require are distributed among a vast network of servers. You almost certainly have no idea where those servers are, how many are involved, or who is managing them – they may as well be within a cloud – but the convenience of accessing the data on any connected computer or mobile device has won over you and millions of other customers.
The problem is that the cost of managing personal or corporate data this way may be privacy and security. For sensitive data to be protected from cloud operators and third parties, it must be encrypted, but if it is encrypted, then cloud servers can’t do anything with it, such as allow you to search and sort it. The tradeoff between security and utility has seemed intractable until last year when the solution was published in the dissertation of Stanford computer science graduate and IBM researcher Craig Gentry (PHD 2009 CS). Gentry’s working scheme for “fully homomorphic encryption (FHE)” still needs some serious efficiency tuning to be practical, but it has been hailed as a breakthrough, earning him the Best Dissertation Award from the Association for Computing Machinery in May.
“Homomorphic encryption gives you a way out of the dilemma,” Gentry says. “It gives you a way to process data without having access to it.”
“Homomorphic” is a mathematical term meaning that if you do two things to a bit of data – say, encrypt it and process it – the order in which you do them won’t matter. In other words, in FHE, data can be processed after it is encrypted, as well as before. This means that a Gmail user could someday send an encrypted search query to the servers in the cloud, and those severs could carry out that query even though the query and the e-mails are completely inscrutable to them. Only the user who holds secret key can ever decrypt the original data, the query, or the query results.
For another example, imagine how FHE could help the proprietor of an online movie streaming service – call it Hackbuster Video-- protect the privacy of customers while still giving them all the features they want. A customer’s request for a new movie would be encrypted, as would the movie itself, meaning that Hackbuster would not know what movie the customer was watching. Despite the privacy, the Hackbuster’s servers could still charge the correct amount, offer playback features such as pause and rewind, and even still make recommendations of similar movies, all without ever being privy to the movies involved.
Gentry’s graduate advisor Dan Boneh, a professor of computer science and electrical engineering, said the work is groundbreaking.
"Craigs construction of the first fully homomorphic encryption solves a key 30-year old problem in cryptography,” Boneh said. “Like climbing Mt. Everest, many have tried to accomplish this feat before and failed. This work will drive research in cryptography for many years to come."
Finding himself, and a brilliant idea
Gentry studied math as an undergraduate but then received a degree from Harvard Law School. He worked as an intellectual property lawyer for less than two years before feeling the math bug again. He convinced the newly formed Palo Alto research office of the Japanese telecommunications firm Docomo to take him on as a cryptography researcher. After a few years feeling much more fulfilled in his new work, Gentry recognized that to stay in the field long-term, he’d need to earn a PhD. He applied to the local college, Stanford, and was accepted.
As a new student he quickly picked up on the challenge laid out by Boneh to tackle the problem of homomorphic encryption. The problem was a famous one in the field – it had been proposed in the late 1970s by developers of the famous RSA public key encryption scheme. Gentry felt he could develop a good approach.
An essential concept in Gentry’s complicated mathematical scheme is that each ciphertext – the name given to data in its encrypted form -- has some “noise” associated with it that obscures which bit – a 0 or 1 – is encrypted. As one adds and multiplies the ciphertexts, so as to add or multiply the bits inside the ciphertexts, the size of the noise grows. As long as the noise does not grow too large, the decryption algorithm can take all the apparent gibberish produced by the operations and recover the bit(s) inside the final ciphertext(s), which contain the desired result of the processing.
For several months, however, Gentry kept facing the same problem. After too many operations, the ciphertexts would eventually become too noisy. The decryption algorithm no longer could unravel the proper answers, because the answers were drowned in noise. It broke down.
“I reached a point of frustration,” he said. “Maybe I can’t get FHE out of this, but what can I do with it?”
In the summer of 2008, when Gentry was interning at IBM, he had an epiphany. The scheme could handle somewhat complicated functions while keeping the data encrypted, but still not very complicated ones. Why not see if the scheme could handle its own decryption function, even while keeping the data secret, to remove enough noise to let the whole process continue?
“That was the ‘aha’ moment,” he said.
Gentry was able to make it work, allowing the process to refresh repeatedly, so that it could accomplish real-world, complex tasks. He calls this self-refreshing property “bootstrapping,” and it was enough to make his homomorphic encryption scheme fully homomorphic.
Before anyone ever puts Gentry’s FHE technology to work, its performance will have to improve, he acknowledges. He and an IBM colleague now have it running on a souped-up laptop, he says, but it is too slow to provide the near-instantaneous use on large sets of data that cloud users would demand.
This month, the U.S. Defense Advanced Research Projects Agency will award $20 million to research groups seeking to develop fast-performing FHE systems. Gentry hopes IBM will win one of the grants. Given that he’s become something of a cryptography celebrity in the past year (e.g. he’s been profiled in Forbes magazine), one would have to think his application will get a thorough read.
