Cryptography Breakthrough Could Make Software Unhackable

https://news.ycombinator.com/item?id=7155371

"It's worth reiterating that this is very much not practical by any standard, and doesn't look anything like the usual software obfuscation used today, even white-box. This thing requires at the very least that multilinear maps and fully homomorphic encryption are anywhere near practical, which is not the case today (and may end up being like quantum computing, always 10 years away)."

With respect to FHE, before 2009 we already had some tools. We had RSA, which is multiplicatively homomorphic (this property is the reason behind the need for good padding!). We also had Paillier, which is additively homomorphic. We even had Boneh-Goh-Nissim, where you could do any number of additions plus one multiplication! In 2009 Gentry completed the picture with a partially homomorphic system, based on lattices, where you could do a number of additions and multiplications before losing "precision". Perhaps more importantly, he also gave us the bootstrapping notion, which allows you to achieve a fully homomorphic encryption scheme from a partially homomorphic one, provided you have enough "precision".

Now, what the article talks about is not strictly covered by Barak's theorem, since it's a different notion (also defined in Barak's paper): indistinguishability obfuscation. Barak proved that black-box obfuscation is impossible in the general case (i.e., for every possible program). Black-box obfuscation is the usual intuitive notion we have of obfuscation: given an obfuscated problem, you can't obtain any more information from it than if you were just querying it as a black-box.

Indistinguishability obfuscation is more subtle: given two different programs that compute the same function, you can't tell whether an obfuscated program is the obfuscation of the first or the second one. This at first sounds pretty useless as an obfuscation scheme, since it gives us few guarantees, but the authors took advantage of this notion to get some useful functionality out of it (namely functional encryption, and later other things).

Even more impressive is the fact that they now have managed to prove that a variant of the original scheme is actually black-box secure [1]. How is this compatible with Barak's result, you ask? The black-box proof of [1] is in the multilinear model, which means it is under the assumption that the attacker can only do a limited set of (algebraic) operations. A poor analogy would be to show that some code obfuscation scheme is secure, but only as long as the attacker is limited to using static analysis.

[1] https://eprint.iacr.org/2013/631