Indistinguishability obfuscation: a basis for all cryptography

“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, an associate professor 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.”