TCC 2014: How to Not Know What You're Doing

After a Wired article prompted a reply by our favorite crypto blogger, it is fair to say that obfuscation is a hot topic at the moment. So it comes at no surprise that TCC started off with not one but two sessions on obfuscation on Monday morning.

Informally, obfuscation means transforming a piece of code such that the transformed code still does the same thing but does not reveal anything about the original code. The formal definition of virtual black-box (VBB) obfuscation uses circuits or Turing machines as code and bit predicates for the security part. And here come the bad news: Barak et al. showed that this is impossible. It follows that a closed-source binary or a piece of "obfuscated" Javascript code can be analyzed to extract for example a private key embedded into it (given enough resources of course).

Is that the end of the story? Not quite. Barak et al. proposed the notion of indistinguishability obfuscation (iO), which postulates that one cannot distinguish between the obfuscated versions of two circuits computing the same function. This is weaker than VBB obfuscation. In more bad news, it is not known how to achieve iO under standard assumptions.

Unsurprisingly, all the papers in the first TCC session were concerned with circumventing the central impossibility result in one way or another. The first paper entitled "Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding" did so by using graded encoding schemes, an idealized model of multilinear maps where the adversary is only allowed to execute public operations and test for zero. The authors use so-called matrix branching programs to construct an obfuscation scheme, which achieves iO and VBB, the latter under a further complexity assumption. The speaker, Zvika Brakerski, stated the opinion that the result might just expose the weakness of the generic model.

The second paper in the session, "Obfuscation for Evasive Functions", went down a different path. The authors restrict the functions computed to so-called evasive functions. These are a family of functions such that random one among them outputs zero with overwhelming probability. An example given in the talk is a patch for a piece of software that crashes on certain inputs. Obfuscation for evasive functions allows to create a patch that rejects those inputs without disclosing on which inputs the software crashes. The authors also work with the virtual gray box model. This differs from the virtual black box model in that it allows for an unbounded simulator. The authors prove various results around the two definitions such as average-case VGB obfuscation for evasive functions implying average-case VGB obfuscation for all function families or average-case VGB obfuscation being equivalent to average-case VBB obfuscation for evasive functions.

Most interesting for MPC folks like me was of course the talk by Shai Halevi in the second session. He presented the paper "Two-round secure MPC from Indistinguishability Obfuscation". The title basically tells it all. They construct two-round MPC from any MPC protocol by obfuscating the parties' computations, which then can be executed by anyone. Because the constructions uses NIZKs, the resulting protocol provides active security. The most intricate part of the construction is the move from security under VBB obfuscation to iO obfuscation. This is achieved by hard-coding the MPC messages into the obfuscation.