A secure foundation for any cryptographic system

“Indistinguishability obfuscation” is a powerful concept that would yield provably secure versions of every cryptographic system we’ve ever developed and all those we’ve been unable to develop. But nobody knows how to put it into practice.

Last week, at the IEEE Symposium on Foundations of Computer Science, MIT researchers showed that the problem of indistinguishability obfuscation is, in fact, a variation on a different cryptographic problem, called efficient functional encryption. And while computer scientists don’t know how to do efficient functional encryption, either, they believe that they’re close — much closer than they thought they were to indistinguishability obfuscation.

“This thing has really been studied for a longer time than obfuscation, and we’ve had a very nice progression of results achieving better and better functional-encryption schemes,” says Nir Bitansky, a postdoc in MIT’s Computer Science and Artificial Intelligence Laboratory who wrote the conference paper together with Vinod Vaikuntanathan, the Steven and Renee Finn Career Development Professor in the Department of Electrical Engineering and Computer Science. “People thought this is a small gap. Obfuscation — that’s another dimension. It’s much more powerful. There’s a huge gap there. What we did was really narrow this gap. Now if you want to do obfuscation and get all of crypto, everything that you can imagine, from standard assumptions, all that you have to do is solve this very specific problem, making functional encryption just a little bit more efficient.”

In computer science, “obfuscation” means disguising the operational details of a computer program so that it can’t be reverse-engineered. Many obfuscation techniques have been proposed, and many have been broken.

So computer scientists began investigating the idea theoretically. The ideal obfuscation scheme would take the source code for a program and rewrite it so that it still yields a working program, but it is impossible to determine what operations it was executing.

Theorists quickly proved that ideal obfuscation would enable almost any cryptographic scheme that they could dream up. But almost as quickly, they proved that it was impossible: There’s always a way to construct a program that can’t be perfectly obfuscated.

Fuzzy details

So they began investigating less-stringent theoretical principles, one of which was indistinguishability obfuscation. Rather than requiring that an adversary have no idea what operations the program is executing, indistinguishability obfuscation requires only that the adversary be unable to determine which of two versions of an operation it’s executing.

Most people recall from algebra, for instance, that a x (b + c) is the same thing as (a x b) + (a x c). For any given values, both expressions yield the same result, but they’d be executed differently on a computer. Indistinguishability obfuscation permits the adversary to determine that the program is performing one of those computations, but not which.

For years, the idea of indistinguishability obfuscation lay idle. But in the last few years, computer scientists have shown how to construct indistinguishability-obfuscation schemes from mathematical objects called multilinear maps. Remarkably, they also showed that even the weaker notion of indistinguishability obfuscation could yield all of cryptography.

But multilinear maps are not well understood, and it’s not clear that any of the proposed techniques for building them will offer the security guarantees that indistinguishability obfuscation requires.