The biggest security breakthrough of 2009 is an IBM software algorithm. (Picture from CNET.)
Created by researcher Craig Gentry, the algorithm solves a seemingly impossible puzzle. How do you let someone else manipulate your secret data while still keeping it secret?
This can be very useful. Companies could get data on a pending deal analyzed by accountants without revealing any details. An online tax service could do your return without its software knowing your income.
Gentry himself understands how desirable this is. He was a Harvard-trained lawyer before deciding his true love was his undergraduate major of math. The breakthrough, called “fully homomorphic encryption,” is his Stanford Ph.D thesis.
The homomorphic is based on the Greek for “the same” (homo) and shape (morphic).
Here is how it works. (The full paper can be found here.)
You put your data into a special encryption box. The encryption is in the form of a lattice, a set of points with a hidden structure where encryption identifies a point in the lattice and decryption finds that point. It’s one of the cleverest forms of encryption we have.
Gentry’s breakthrough lets a computer do a second encryption on that lattice, essentially putting it into a second box so it can be worked on, then re-encrypts it so the original key fits. Most of his paper describes how the underlying math works.
Standard encryption uses a system of public and private keys. You can publish the public key, which is used to generate any number of one-time use private keys. Gentry’s system envisions a series of private keys, each created using the key before it by the computer messing with your secret data.
This solves a big problem with homomorphic encryption systems, data files growing as they are encrypted into the lattice. This “perfect” homomorphism problem was seen as impossible to solve by Ronald Rivest, the encryption legend (the R in RSA encryption systems we use today) who first imagined it 30 years ago.
Gentry solved Rivest’s impossible problem.
A recent Business Week profile of Gentry says he was an “intern” in 2008, but this use of the term is a plot device. He was in fact a Ph.D candidate doing a three-month turn at IBM’s Watson Center in order to work on his thesis. He was no more an intern than Kenneth is a page on 30 Rock.
It will take years to turn Gentry’s breakthrough into a product. It needs to be tested more thoroughly, then coded, then beta tested, before anyone starts depending on it.
Gentry also has his critics, like security expert Bruce Schneier, who calls it “completely impractical” with present technology, and thinks IBM is over-hyping its near-term implications. Still, he calls Gentry’s paper “an amazing piece of work.”
We now have the promise of a new era in cryptography, an added layer of security that comes along just once in a generation. Even if it takes years to make the lock we have the key to it and that’s what counts.
