Progress and Challenges in Code Obfuscation (part I/II)

(joint post by Yael Kalai and Guy Rothblum)

It feels especially appropriate to write about recent developments in cryptography and code obfuscation while basking in the afterglow of a wonderful workshop at the Weizmann Institute of Science, celebrating the work of Shafi Goldwasser and Sivio Micali—this year’s Turing Award recipients. Shafi and Silvio repeatedly demonstrated that in cryptography we can obtain seemingly impossible or self-contradictory goals, such as zero-knowledge proofs that convey no information beyond their validity, or pseudorandom functions whose input-output behavior appears completely random (even though they have a succinct description).

Our blog post is about another such “pie in the sky” problem in cryptography: code obfuscation. The question at hand is whether one can transform a program (say, described as a Boolean circuit), maintaining its input/output behavior but making it otherwise unintelligible. This problem was originally formalized by Barak et al. [BGI+01] (following earlier work by Hada [Hada00]). However, rather than providing tools to obfuscate programs, Barak et al. gave impossibility results.  They considered the natural definition of virtual-black-box obfuscation (VBB-Obf): anything that can be computed efficiently given a program’s obfuscation, should be efficiently computable from black box access to the program.  This natural definition is quite strong, and in particular general-purpose VBB-Obf (under the “right” formalization) has fantastic cryptographic applications. Unfortunately, Barak et al. proved a strong negative result, showing that general-purpose VBB obfuscation is impossible. Namely, they constructed a (contrived) function family for which there exists a PPT adversary that given *any* code of a function f in the family, can find the secret key associated with f, whereas this key remains completely hidden given only black-box access to f.  Thus, access to the code is *very different* from black box access, and the family seems very difficult to obfuscate in any meaningful sense.

Following this thought provoking work, much effort has been devoted by the cryptographic community to constructing obfuscators for natural classes of programs.  However until recently, all known obfuscation candidates were for limited classes of functions, such as (for example) point functions [Canetti97] (functions that are zero everywhere except for a single input), variants of point functions, hyper-planes [CRV10], conjunctions [BR13a], and CNFs [BR13b]. It was not clear how to extend these works to get obfuscation for more complex classes of functions, and until recently there weren’t even suggestions for candidates or heuristics.

This changed with a fascinating recent work of Garg et al. [GGHRSW13]. They propose a candidate general-purpose program obfuscator.  Namely, they construct an obfuscator, that takes as input any program (or circuit) and outputs another program (or circuit) that has the same functionality as the input program, and seems to hide secret information.  The big question is whether this candidate construction indeed has a “meaningful” secrecy guarantee. One can simply assume that the [GGHRSW13] obfuscator is secure.  However, due to the negative result of [BGI+01], assuming that the [GGHRSW13] obfuscator always offers a “meaningful” security guarantee is simply false.

To bypass these negative results, [GGHRSW13] study the possibility that their obfuscator is an indistinguishability obfuscator (Ind-Obf); i.e. that given any two circuits C and C’ of the same size that compute the same functionality f, no polynomial time adversary can distinguish between the obfuscation of C and the obfuscation of C’. There are no known impossibility results for Ind-Obf. Indistinguishability obfuscation provides an intuitively appealing notion of security via an equivalence to “best possible” obfuscation, a notion put forth by Goldwasser and Rothblum [GR07].  This notion makes the relaxed requirement that the obfuscated program leaks as little information as any other program with the same functionality (and of similar size). Further, in a fascinating recent work, Sahai and Waters [SW13] show that Ind-Obf has many exciting cryptographic applications (e.g. deniable encryption [CDNO97]).

In [GGHRSW13], and in followup works [BR13c,BGKPS13], there is some evidence that this obfuscator and variants of it do have some secrecy guarantees. The obfuscator of Garg et al. makes use of multi-linear maps, a powerful new cryptographic tool introduced by [GGH13]. Loosely speaking, such maps allow one to encode elements in a way that one can efficiently add encodings, multiply encodings (a bounded number of times), and check whether an encoding is an encoding of zero. [BR13c] prove that a variant of the [GGHRSW13] obfuscator does indeed satisfy the Ind-Obf definition if the adversary is limited to “algebraic” attacks, which means that it can only add and multiply the multi-linear encodings, and check whether an encoding is an encoding of zero, but cannot do anything else with these encodings. I.e., they prove security for a limited class of attackers. Moreover, [BR13c,BGKPS13] show that variants of the construction even satisfy the stronger VBB-Obf definition for “algebraic” attacks.

Of course, the attentive reader may be left puzzled by this state of affairs, as Barak et al. showed that satisfying VBB-Obf is impossible! There is no contradiction, because there is no reason for attackers to limit themselves to algebraic attacks.  For example, an attacker can feed the obfuscated circuit (which contains these encodings) as input to another circuit.  Barak et al. [BGI+01] make use of such attackers to obtain their negative results.

To summarize (and interpret) the recent developments:

• Using powerful new cryptographic tools (multilinear maps), Garg et al. present a candidate for obfuscation that may provide meaningful security guarantees.
  Namely, it is a candidate for Indistinguishability Obfuscation, which provides an appealing semantic notion of “best possible security”, and has exciting cryptographic applications.
• There is some evidence for the security of this construction and variants of it: we have obfuscators that provably resist the rich family of “algebraic attacks”.
• We know that adversaries may mount non-algebraic attacks against obfuscators, and indeed restricting our attention to algebraic attackers lets us bypass known impossibility results.
• It is an outstanding open problem to either prove the security of an Indistinguishability Obfuscator under standard assumptions (or under any “falsifiable” assumption), or to show impossibility for general-purpose Indistinguishability Obfuscation.

In a follow-up post, Yael will describe even more recent work that leads her to be pessimistic about the possibility of obtaining strong positive results on obfuscation for many natural classes of functions.

In conclusion, there have been many exciting recent developments in cryptography (perhaps most notably in the study of fully homomorphic encryption), and it appears that we may be on the brink of another exciting wave of developments in the study of code obfuscation. At the very least, there are fascinating new foundational problems for the field to study.

Going back to the Weizmann workshop, one recurring theme in this workshop was participants recounting how, again and again, the question has been raised: “what is left to do in cryptography?” (As early as the early 80’s). Again and again, however, we are surprised and delighted by new conceptual and technical breakthroughs in the field. Nowadays it seems clear that while much has been done in cryptography, even more remains to be explored.

References

◾[BGI+01] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (im)possibility of obfuscating programs. Crypto 2001, Journal of the ACM 2012
◾[BGKPS13] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, Amit Sahai: Protecting Obfuscation against Algebraic Attacks. CRYPTO ePrint 2013
◾[BR13a] Zvika Brakerski, Guy N. Rothblum: Obfuscating Conjunctions. CRYPTO 2013
◾[BR13b] Zvika Brakerski, Guy N. Rothblum: Black-Box Obfuscation for d-CNFs. ITCS 2014
◾[BR13c] Zvika Brakerski, Guy N. Rothblum: Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding. TCC 2014
◾[CDNO97] Ran Canetti, Cynthia Dwork, Moni Naor, Rafail Ostrovsky: Deniable Encryption. CRYPTO 1997
◾[Canetti97] Ran Canetti: Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information. CRYPTO 1997
◾[CRV10] Ran Canetti, Guy N. Rothblum, Mayank Varia: Obfuscation of Hyperplane Membership. TCC 2010
◾[GGH13] Sanjam Garg, Craig Gentry, Shai Halevi: Candidate Multilinear Maps from Ideal Lattices. EUROCRYPT 2013
◾[GGHRSW13] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, Brent Waters: Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. FOCS 2013
◾[GR07] Shafi Goldwasser, Guy N. Rothblum: On Best-Possible Obfuscation. TCC 2007
◾[Hada00] Satoshi Hada: Zero-Knowledge and Code Obfuscation. ASIACRYPT 2000
◾[SW13] Amit Sahai, Brent Waters: How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. CRYPTO ePrint 2013