Progress and Challenges in Code Obfuscation: Part II

This is a followup to the previous post on program obfuscation written jointly with Guy Rothblum.

The problem of program obfuscation is fascinating.  The question at hand is whether one can transform a program (say, described as a Boolean circuit) into a form that is executable (i.e., has the same input/output behavior), but is otherwise completely unintelligible.  This problem was originally formalized by Barak et al. [BGI+01], who constructed (contrived) function families that are not obfuscatable under the natural definition of virtual black box (VBB) security, as well as various relaxations.  Loosely speaking, VBB security requires that anything that can be efficiently computed given an obfuscation of a program could be efficiently computed from black box access to the program.

The result of Barak et al. (and followup work [GK05]) left researchers quite pessimistic about solving the general problem of program obfuscation, and (until recently) most of the effort was on obfuscating very simple functions, such as 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].

The challenging and cryptographically meaningful function families to obfuscate are those that have high “pseudo-entropy”.  Extreme examples are pseudo-random functions and decryption algorithms. Note that it is trivial (and uninteresting) to obfuscate functions that are learnable from black-box access.

The focus of the previous post was on recent exciting progress on program obfuscation, initiated by the fascinating recent work of Garg et al. [GGHRSW13], which gave the first plausible candidate for general-purpose obfuscation.  They conjectured that it is an indistinguishability obfuscator; i.e., given any two circuits C_1 and C_2 of the same size and computing the same function, no polynomial time adversary can distinguish between the obfuscation of C_1 and that of C_2.  Unfortunately, it is not clear how meaningful this notion is, since an indistinguishablity obfuscator does not guarantee to hide the secrets of the underlying program (or circuit); indeed, as we know from [BGI+01] there are function families that can always be reverse engineered. One of the motivations of indistinguishability obfuscation is that it was proven to be equivalent to “best possible” obfuscation by Goldwasser and Rothblum [GR07].

The work of Garg et al. gave optimism to many cryptographers, and several tried to analyze and prove security of their construction (and its variations) [GGHRSW13,BR13c,BGKPS13], with limited success.  To date, a variant of the construction is known to be VBB secure against a subclass of adversaries, known as algebraic adversaries.  However, we have no evidence as to its security level against non-algebraic adversaries.  Moreover, as mentioned above, even if we were able to prove that it is an indistinguishability obfuscator, it is still unclear how meaningful it is.

Nevertheless, to my surprise, subsequent to [GGHRSW13] a flood of results have appeared showing that indistinguishability obfuscation suffices for many other cryptographic applications, such as the construction of public-key encryption from private-key encryption, the existence of deniable encryption, multi-input functional encryption, multiparty key exchange, broadcast encryption, traitor tracingand, more [SW13,GGHRSW13,HSW13,GGJS13,BZ13,BCP13,BCPR13].

Unfortunately, in this post, we diverge from the optimistic view of the crowd.  In a somewhat strange twist, in joint work with Cohn and Goldwasser [CGK14], we show that there are negative implications of [GGHRSW13] to accompany the positive ones.   In particular, we show the existence of indistinguishability obfuscation implies strong limitations on the possibility of VBB obfuscation with a universal simulator for any function family with high pseudo-entropy.  What is VBB simulation with a universal simulator?

The Barak et al. definition of VBB obfuscation of a circuit family requires that for each probabilistic polynomial-time (PPT) adversary A there exists a PPT simulator S that succeeds in simulating the output of A, when A is given the obfuscated circuit but S is given only black-box access to the circuit. Unfortunately, this definition does not say how hard (or easy) it is to find this simulator S. This sufficed for the Barak et al. work, as they were after showing impossibility results and thus were happy to work with an obfuscation definition that didn’t address how one may find S.

A stronger and arguably more meaningful definition requires that there exist a *universal* PPT simulator capable of simulating any PPT adversary A given the code of A.  Such a definition is referred to as VBB with a universal simulator. Ideally, we would like to construct an obfuscator that is VBB secure with a universal simulator.  However, given the negative result of [BGI+01] we know that we cannot hope to construct such an obfuscator for all function families, and we must focus on specific function families.  That said, it may be the case that all “natural” function families are obfuscatable.

In [CGK14] we show that assuming the existence of indistinguishable obfuscation, <strong>all</strong> function families with super-polynomial “pseudo-entropy” cannot be VBB obfuscated with a universal simulator.  Informally, a function family has super-polynomial pseudo-entropy if given black-box access to the function it appears to have super-polynomial min-entropy.  Such families include all pseudo-random function families, as well as every semantically secure secret-key and public key encryption scheme, or any secure digital signature scheme (where randomness is generated by using a pseudo-random function).

We obtain this result by exploiting a connection between obfuscation with a universal simulator and obfuscation with auxiliary inputs, and by showing new impossibility results for obfuscation with auxiliary inputs.

In light of this, where should we be heading?  It seems that in the quest for positive results, we should either restrict our attention to function families that do not have super-polynomial pseudo-entropy, or try to bypass these negative results by considering relaxed definitions of security.  If we stick to our goal of VBB security for functions with super-polynomial pseudo-entropy, we will need to use non-black techniques where the simulator uses the adversary in an inefficient manner.  To my knowledge, to date such a technique was used only once, in [Canetti97].

A class of functions that would be interesting to study which do not have super-polynomial pseudo entropy are evasive function families, which are functions that are zero almost everywhere, and any PPT adversary who is given oracle access to a random function in the family cannot find a non-zero input.  We have no negative results for such families, and some partial positive results are known [BBCPKS13].  

These are fascinating questions and I am excited to see new developments in the upcoming months.

References:

[BBCPKS13] Boaz Barak, Nir Bitanski, Ran Canetti, Omer Paneth, Yael Tauman Kalai, Amit Sahai: Obfuscation for Evasive Functions. Cryptology ePrint Archive, Report 2013/ 668

[BGKPS13] Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, Amit Sahai: Protecting Obfuscation against Algebraic Attacks. Cryptology ePrint Archive, Report 2013/631

[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

[BCPR13] Nir Bitansky,Ran Canetti,Omer Paneth, Alon Rosen: Indistinguishability Obfuscation vs. Auxiliary-Input Extractable Functions: One Must Fall. Cryptology ePrint Archive, Report 2013/641

[BZ13] Dan Boneh, Mark Zhandry: Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation.  Cryptology ePrint Archive, Report 2013/642

[BCP13] Elette Boyle, Kai-Min Chung, Rafael Pass: On Extractability Obfuscation. Cryptology ePrint Archive, Report 2013/650

[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

[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

[CGK14] Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai: The Impossibility of Obfuscation with a Universal Simulator.  IACR Cryptology ePrint Archive, Report 2013/665

[GGHRSW13] Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, Brent Waters: Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. FOCS 2013

[GGJS13] Shafi Goldwasser, Vipul Goyal,Abhishek Jain, Amit Sahai: Multi-Input Functional Encryption. IACR Cryptology ePrint Archive, Report 2013/727

[GK05] Shafi Goldwasser, Yael Tauman Kalai:  On the Impossibility of Obfuscation with Auxiliary Input.  FOCS 2005

[GR07] Shafi Goldwasser, Guy N. Rothblum: On Best-Possible Obfuscation. TCC 2007

[HSW13] Susan Hohenberger, Amit Sahai, Brent Waters: Replacing a random oracle: Full domain   hash from indistinguishability obfuscation.  IACR Cryptology ePrint Archive, Report 2013/509

[SW13] Amit Sahai, Brent Waters: How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. IACR Cryptology ePrint Archive, Report 2013/454