A New Design for Cryptography’s Black Box

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.

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.

IO would be comically impractical to use today. Any encryption scheme is going to slow down a program at least a little. In the case of IO, the mountain of equations needed to achieve indistinguishability slows things down a lot.

“It probably takes hundreds of years to obfuscate and run a program,” said Vinod Vaikuntanathan, a cryptographer at the Massachusetts Institute of Technology who has been heavily involved in IO research. “When it becomes that ridiculous you stop caring about the exact numbers.”

One general strategy taken by computer scientists to speed up running times has been to reduce obfuscating one large program to obfuscating connected smaller programs. As computer scientists envision it, obfuscating a program would require two steps. Improvements in either step could increase efficiency overall.

The first step is the harder one. Current IO methods begin with a so-called “bootstrapping” program that is small enough to obfuscate. This program interacts with the large “target” program. The bootstrapping program acts like a secure bubble around the target program’s inputs and outputs — it obfuscates anything that comes in and out of it, effectively obfuscating the target program as a whole.

Yet no one has figured out how to efficiently obfuscate even the small bootstrapping program. It’s like trying to find the “first chink in the armor,” Sahai said. “The bootstrapping program is where we’re really stuck.”

Researchers have made more progress on the second step. Once the bootstrapping program is in place, the challenge is to obfuscate longer and more varied kinds of computations. At the annual Symposium on Theory of Computing (STOC) in Portland, Ore., in June, three teams of researchers presented work that demonstrated how to go from obfuscating any single circuit — which researchers already knew how to do in theory — to obfuscating a general-purpose computer (or Turing Machine, in the eyes of theoretical computer scientists).

It’s a big leap. In order to obfuscate a circuit, researchers need to know the size of the input and every step in the computation ahead of time. Computers, by contrast, are set up to read arbitrarily long inputs, making additional computations as more data come into view. The work presented at STOC showed how to use a technique called punctured programming to obfuscate these longer, open-ended calculations as a series of discrete, connected, circuit-size steps.

“The main technical achievement applies IO for circuits to the local steps of a computation and ties things together so you are protecting the computation globally,” said Allison Bishop, a computer scientist at Columbia University who co-authored one of the papers presented at STOC.

Mathematically Proven Security

Making IO more efficient would address a practical problem. Establishing that it’s highly secure would solve a fundamental one.

When Sahai and Brent Waters, a computer scientist at the University of Texas, Austin, described a way to use IO in 2013, it was largely a matter of belief that this style of obfuscation would protect the secrets inside a program. Their initial work was kind of like tying a very complicated-looking knot — it might appear very tough to undo, but without really understanding the structure of the knot, it’s hard to be sure there isn’t some simple way of unwinding it.

“At that point there was just a construction, it wasn’t even clear how to argue security,” Vaikuntanathan said. “There was no clue how to go about it.”

The situation has improved since then. Any good cryptography scheme rests on a mathematical foundation that defines the problems the intruder would have to solve in order to break the code. RSA encryption, for example, uses the product of two large prime numbers. To start reading your emails, an intruder would have to work backward from that product and identify the two primes that were multiplied to produce it — a task that’s understood to be impossible given the limits of current computing power.

The mathematical assumptions underlying a cryptography scheme need to be hard. They should also be simple, long-tested, and well-understood, so that cryptographers can be confident that a problem is as difficult as it looks.

“It has to be a mathematical problem we can understand. Otherwise experience has taught us that it’s likely to get broken,” Sahai said.

In 2013 there were no practical security assumptions behind IO. A year later, in April 2014, Waters, Bishop and Craig Gentry, a research scientist at the IBM Thomas J. Watson Research Center in Yorktown Heights, N.Y., released a pair of papers boiling the problem of IO down to a set of simple assumptions related to a type of mathematical object called multilinear maps. (Sahai was a co-author on one of the papers.) “We said if the attacker breaks [IO] in any way, he must be solving one of these problems,” Bishop said.

Yet multilinear maps were only introduced into cryptography in 2013. Experts haven’t had time to rigorously assess how reliable they are. “Right now, if these multilinear-map candidates got broken, you wouldn’t shock the world,” Waters said.

Currently, computer scientists are trying to figure out how to replace multilinear maps with a better-understood mathematical obstacle. The best hope seems to be “learning with errors” (LWE), a problem in machine learning. LWE and multilinear maps share a common mathematical ancestry in a field called lattice-based cryptography, which is why one seems like a good candidate to replace the other. However, no one has figured out how to make the leap.

“It’s like looking across a cliff. It’s so close, it looks like I can jump across it, but that really isn’t the case,” Vaikuntanathan said.

The Security Rush

Despite the challenges facing IO as a field, experts express confidence that an IO-based security scheme is coming. Sahai points out that the lag time in cryptography from idea to implementation has been as high as 30 years. Given the pace of progress that’s been set in the last two years, he thinks IO could be ready much sooner than that. “We’re hoping to shorten it to 10-15 years,” he said.

The major milestone to watch for is the establishment of a simpler mathematical basis for IO security. The most prominent figures in the field think the circumstances are right for IO adoption to move quickly. Bishop said she “wouldn’t bet against” a simple set of hard security assumptions developing in less than a decade. Vaikuntanathan is even more bullish. “I would even go so far as to say a couple years.”

The optimism owes in part to all the resources that have flowed into IO research over the last two years. Sahai now serves as the director of the Center for Encrypted Functionalities at UCLA. The center, which is devoted to obfuscation research, was founded in 2014 and is funded by a $5 million grant from the National Science Foundation, with Waters and Bishop as co-principal investigators. Also last fall, the Defense Advanced Research Projects Agency (DARPA) announced the creation of SafeWare, a research program that supports the creation of “highly efficient and widely applicable program obfuscation methods with mathematically proven security properties.”

The rush to develop IO speaks to its power but also to the cat-and-mouse game intrinsic to cryptography. At the same time that researchers are developing new security strategies, others are hard at work on quantum computers. If and when they arrive, their computing speed will lay waste to most existing cryptographic schemes. Except — perhaps — for IO.

* Quantum-secure cryptography is a tricky subject; no methods have been proven to be completely secure from quantum-based algorithms. [return]

This article was reprinted on Wired.com.