IBM's Encryption Breakthrough for the WebStephen Baker
In the dog days of summer 2008, an intern at IBM Research was sitting in a Manhattan café turning a problem over in his head. Craig Gentry was thinking about cryptography, the science of codes and data protection, tussling with a question that had confounded the world's greatest mathematicians for three decades. Is it possible to run calculations on encrypted data without actually decrypting it?
Then Gentry had an idea. He thought of boxes enclosed within other boxes. That idea led to a breakthrough, a solution, at least in theory, to the elusive question so many had pondered before. Gentry, a Stanford University PhD candidate, was hardly an iconic math prodigy; he was nearly 35 years old at the time. His is a story of exploration and discovery not only in mathematics, but also in his career.
Just last year Gentry got a three-month internship at IBM's (IBM) Thomas J. Watson Research Center in Yorktown, N.Y. His breakthrough in encryption could allow people to share their data and keep it secret at the same time. If it works, this so-called fully homomorphic encryption would enable consumers to carry out many of their online activities, from e-commerce to banking, without disclosing the numbers or details of the private information involved. Gentry describes it as submitting to surgery without even having to take off your clothes—or identifying yourself to the doctor. This type of protection, again if it works, could bring a crucial layer of safety and privacy to the online world, encouraging people to entrust more of their lives, from banking to health care, to the networks.
Years from the Marketplace Don't expect such changes overnight. Gentry's breakthrough, unveiled by IBM in June, is still years from the marketplace. It involves lots of cloaking and uncloaking of data, which eats up far too much computing power for now. Still, IBM officials are describing the nascent technology in expansive terms. J.R. Rao, who leads the Secure Software & Services Group at IBM, says that this new encryption could enable vast new areas of commerce and medicine to migrate safely to cloud computers. With the development of mobile devices, that would put all of our data, including the most sensitive, at our fingertips at every moment. He compares Gentry's invention to the Wright brothers' first flight in Kitty Hawk, N.C.—a demonstration of the possibility of something big, though not yet commercially viable. "It has a huge number of applications," he says.
Gentry, who has since been hired by IBM (while still putting the finishing touches on his PhD thesis), took a circuitous route to the summit of research in applied mathematics. A math major in college, he went on to law school at Harvard University. Ten years ago he was working at a New York law firm and specializing in intellectual property.
He didn't like the work and began itching to return to math. One day, after about a year and a half as a lawyer, he reworked his résumé to emphasize his math skills and posted it. This was at the height of the dot-com boom, and the market for math was booming. Gentry landed a job at the Silicon Valley labs of NTT DoCoMo (DCM), the Japanese giant in mobile telephony.
Cryptography Vital to E-Commerce It promptly put him to work in cryptography. This was vital to DoCoMo, the world leader at the time in mobile e-commerce. If people were going to continue migrating their shopping and banking to handsets, the data needed to be safely encrypted.
At this point, Gentry had already taken one detour into law. You might think that someone intent on pursuing a career in mathematical computer science would stop only briefly at a cell-phone lab. After all, he only had a bachelor's degree in math. But he liked the cryptography and, he says, "I'm lazy about looking for jobs." He stayed put at DoCoMo for five years.
It wasn't until he was in his 30s, in 2005, that Gentry enrolled in graduate studies at Stanford in computer science. And in the summer of 2008, he headed east for his three-month summer internship at IBM. By then, many cryptographers viewed a fully homomorphic system as impossible. They had devised systems to carry out operations on encrypted data. But each one was partial. In some, users could multiply the encrypted numbers without decrypting them. In others, they could add such numbers. A fully homomorphic system would permit them both to add and to multiply the data.
Why such a fuss about conducting operations on encrypted data? Consider an analogy from the physical world. A toilet breaks in a Beverly Hills mansion. The old, reliable plumber is on vacation. Can the owners trust the new one? Who knows? Maybe he'll slip a Ming Dynasty goblet into his pocket. Maybe he's casing the joint for a crime ring. In Gentry's scheme, the untrusted person can carry out the work without seeing the data. It's as if the plumber can fix the toilet without even setting foot inside the mansion.
"Completely Impractical," Says a Critic The challenge cryptographers face in devising such a scheme has to do with distortion. Carrying out calculations on encrypted data introduces slight distortions. With lots of calculations, which are necessary for such convoluted digital peek-a-boo, the distortion grows enough to render the data useless. Gentry's idea at the coffee shop was to give the encrypted data a double-wrapping of protection and to have most of the calculations, and distortion, affecting the outer layer. "Boxes inside of boxes" is his description of the approach.
No doubt these boxes are convoluted. But without powerful systems to protect data online, millions are sure to stick with the inefficient tried-and-true. "It's really hard to build trust out of whole cloth online," says Jules Cohen, director of online privacy and safety for Microsoft (MSFT). So while a successful social network such as Facebook can attract 300 million customers, Mint.com, one of the fastest-growing personal finance sites, has only 1.5 million. Intuit (INTU) bought Mint weeks ago for $170 million. With widespread confidence in encryption, both the number of subscribers and the dollar value of that site (among many others) could skyrocket.
To be sure, opening and shutting all of Gentry's boxes with cryptographic keys involves lots of computing power. Bruce Schneier, a security technologist and author, blogged in July that Gentry's breakthrough was "completely impractical." He said the necessary computing would require decades of advances in both computer speed and optimization.
"People will find a way to reduce the complexity of the scheme," Gentry responds. He says that in recent months he has already managed to trim down the algorithm—though he still has far to go. Readying his formula for the applied world, he says, will require a few breakthroughs but nothing on the order of his original discovery. While he doesn't hazard a guess on the timing, he likes the work. Simplifying his encryption scheme, he says, "is an interesting problem, but not as interesting as the first one."