DAVIDOPE FOR QUANTA MAGAZINE
In July 2013 a pair of studies set the cryptography world on fire. They were posted within days of one another to an online archive where researchers share their work, and together they described a powerful new method for hiding the secrets inside software programs.
Original story reprinted with permission from Quanta Magazine, an editorially independent division of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences
The method was called “indistinguishability obfuscation,” or IO. The authors touted it as a “central hub” for all of cryptography—a unified basis upon which to reconstruct familiar cryptographic tools like public keys and selectively secure signatures. The papers also took a first stab at demonstrating what IO might look like mathematically.
The research produced a flurry of interest at the time, but in the two years since the announcement, computer science researchers have encountered a number of practical challenges that stand in the way of using IO. For one thing, IO is extraordinarily slow. Obfuscating a program adds delays that would be measured not in minutes or hours, but in lifetimes. In addition, the method is not nearly as mathematically secure as it needs to be.
But in the past few months, a number of studies have provided some of the most important advances since the 2013 announcement. Some researchers now think we could get a working system in a decade, or maybe even sooner than that. “As of right now it seems like there are no big limitations,” said Amit Sahai, a computer scientist at the University of California, Los Angeles, who was a co-author on both of the papers. “IO is powerful and can do almost anything we’ve ever wanted to do.” And if IO can be constructed in terms of certain simple mathematical assumptions, researchers believe that even a quantum computer couldn’t break it.*
A Mountain of Small Steps
Indistinguishability obfuscation begins by positing two programs that compute the exact same outputs by different methods — for example, the equivalent functions f(x) = x(a + b) and f(x) = ax + bx. For any set of three inputs—a, b and x—each program produces the same result as the other, but arrives at that result by a different path. IO says that given two equivalent programs, it should be possible to encrypt them so that users cannot tell which version they have, no matter how much they poke around.
The 2013 papers convinced many people that IO has the power to dramatically broaden the scope of cryptography. But the studies didn’t specify how to make the idea practical. Researchers have two primary challenges: First, to speed up the process. And second, to ensure that IO is secure.