Two years ago, IBM researcher Craig Gentry revealed that he’d cracked a 30-year old theoretical problem in cryptography: How to perform complex computations on encrypted data without decrypting it. That seemingly magical trick would allow a computer to manipulate a user’s scrambled information without ever violating its secrecy, a potential privacy breakthrough that’s particularly enticing in an era of outsourcing and cloud computing.
Turning Gentry’s innovative but impractical crypto scheme into a workable product, on the other hand, will take years’–or even decades’–more work. But to the defense and intelligence research agencies DARPA and IARPA, that sounds like just the sort of ambitious challenge worth tackling.
On Tuesday, the Defense Advanced Research Projects Agency announced that it’s awarded around $5 million to the Portland-based research contractor Galois to work on that cryptographic problem. Sally Browning, the principal investigator for Galois’ DARPA work, tells me that’s just a part of the $20 million DARPA plans to dish out over five years to contractors and academic research teams as part of a program called Programming Computation on Encrypted Data. (In DARPA’s strange acryonym language, the program is abbreviated PROCEED.) IARPA, DARPA’s intelligence counterpart, in December issued a call for proposals for a similarly-focused project called SPAR, or Security And Privacy Assurance Research.
Both SPAR and PROCEED aim to work out a way to both encrypt data and let it be used and manipulated. SPAR’s program announcement offers the example of building a database in which a user can make a query that the database accurately answers without ever learning the content of that request. Other examples might be a search engine that finds results on the Web without ever seeing a readable search term, or a voting system that can tally ballots without ever looking at them in an unencrypted form.
Those cryptographic sleights of hand may sound logically impossible. In fact, this sort of computable encryption, what cryptographers call “full homomorphic encryption,” was proposed three decades ago by cryptographers Ron Rivest, Leonard Adleman, and Michael Dertouzos but remained a long-unsolved problem. That is, until IBM researcher Craig Gentry published an elegant solution in June of 2009.
I wrote about Gentry’s paper at the time in this article for the magazine. Gentry is quoted comparing fully homomorphic encryption to “one of those boxes with the gloves that are used to handle toxic chemicals.”
“All the manipulation happens inside the box,” he says, “and the chemicals are never exposed to the outside world.”
On Wednesday, Gentry’s work earned him the Association for Computing Machinery’s Grace Murray Hopper Award, one that’s formerly been given to luminaries like Ray Kurzweil, Steve Wozniak and Bob Metcalfe.
But there’s still a major hurdle for Gentry’s method: It takes immense computational power. A single Google search, for instance, would take about one trillion times as long with fully homomorphic encryption as it would in its unencrypted form.
DARPA and IARPA’s contractors will seek to find new, more efficient ways to implement schemes like Gentry’s. According to DARPA’s guidelines, its goal is to reduce the computing time for fully homomorphic encryption by a factor of 10 million compared to its current state, or alternatively to reduce it to 100,000 times the computation required for unencrypted computing.
When I spoke with Gentry, he said he already has some tricks up his sleeve. He’s recently discovered a new version of the fully homomorphic scheme that’s still very inefficient, but may be more open to computational shortcuts. (He declined to share more details before the paper can be published.) “It’s a very different approach,” says Gentry. “It adds more flexibility that might let it be better exploited.”
What are the odds that Gentry’s new method will unlock fully homomorphic encryption for practical use? “When I have an idea, its probability of working is usually about one percent,” says Gentry with a chuckle.
Judging by that success rate from the inventor of fully homomorphic encryption himself, DARPA, IARPA, and their contractors will have plenty of work ahead.