Technical Perspective: A Breakthrough in Software Obfuscation

To view the accompanying paper, visit doi.acm.org/10.1145/2902313

For thousands of years, cryptography was synonymous with "secret writing" whereby two parties used some shared secret key or method to communicate confidential information. But beginning in the 1970s, there was an explosion of new cryptographic concepts and applications. These include public key cryptography—confidential communication between two parties over an open channel, secure function evaluation—jointly computing a function of private inputs (such as the results of an election or auction) without revealing them, zero knowledge proofs—proving a statement is true without revealing anything else, fully homomorphic encryption—computing on encrypted data, and more.

These notions seem so paradoxical it is amazing these cryptography pioneers even imagined they could ever be achieved!^a Based on their writing, it seems at least part of these inventors’ thought process involved the following mental experiment: it not too difficult to convince yourself these wonderful objects can in fact be achieved if we had a black box computing some function, whereas every party could use the box to compute an output from an input but cannot understand its internal working. In the words of James Ellis,^b "we can regard our [encryption function] as a look-up table containing one value of output for each possible input value." The hope was it would be possible to simulate such a program by using what Diffie and Hellman called a "one-way compiler, which takes an easily understood program in a high-level language and translates it into an incomprehensible program in some machine language."^c

Such a compiler is known as a software obfuscator, and despite serving as a guiding light as to what cryptographic tools we can hope to achieve, in the many years since, most practical and theoretical results on this notion have been negative. Obfuscation was and still is practiced to protect intellectual property and other secrets in source code, but no practical scheme has been found that resists a truly determined attacker. On the theory front, in 2001 my co-authors and I showed that for arguably the most natural notion of obfuscation, known as "virtual black box" obfuscation, is impossible to achieve.^d We left a "tiny" loophole by noting it did not rule out a weaker notion known as "indistinguishability obfuscation" or IO. However, at least to me it seemed this notion of IO may well be also impossible to achieve and even if it was achievable, it did not seem very useful. The following paper of Garg et al. proved I was probably wrong on the first count and definitely wrong on the second one.

In this remarkable work, the authors construct a "one-way compiler" of the type envisioned by Diffie and Hellman. This is a way to transform a program P into a program Q that is functionally equivalent, in the sense it would produce the same output as P on every input, but is "incomprehensible" in the sense it satisfies this IO condition. The compiler itself is very different than all prior obfuscators. It is based on another breakthrough paper by a subset of these authors,^e who constructed an object known as "cryptographic multilinear maps." They combine this with a result of Barrington^f that originally arose in the context of circuit lower bounds. The resulting compiler can be thought of as somewhat analogous to converting the program P into a scrambled Rubik’s cube. If you interpret the input x as a sequence of rotations to apply to the cube, the final pattern will convey the output P(x). But you will not be able to learn any other information from it.

The second contribution of this paper was to show this seemingly weak notion of IO is in fact sufficiently strong to obtain some of the most exciting applications of obfuscation. This has been greatly extended in many follow-up works, which have established IO as a kind of a "cryptographic master tool" that can yield a great many other applications.

This paper opens many more research directions than it closes. For starters, while the authors gave some evidence for the security of their construction, it is not truly satisfying, and basing IO on firmer foundations is a crucial research objective. Also, at the moment the construction is terribly impractical, incurring a huge blowup to even the simplest programs. Both of these and more are now the object of intensive research efforts. It truly is an exciting time for cryptography.

Back to Top

Back to Top