
Research
Abstracts  2007 
On BestPossible ObfuscationShafi Goldwasser & Guy N. RothblumOverviewAn obfuscator is a compiler that transforms any program (which we view as a boolean circuit) into an obfuscated program (also a circuit) that has the same inputoutput functionality as the original program, but is otherwise “unintelligible”. Obfuscation has applications for cryptography and for software protection. Barak et al. [1] initiated a theoretical study of obfuscation, which focused on blackbox obfuscation, where the obfuscated circuit should leak no information except for its (blackbox) inputoutput functionality. A family of functionalities that cannot be obfuscated was demonstrated. Subsequent research [2] has showed further negative results as well as positive results for obfuscating very specific families of circuits, all with respect to black box obfuscation. We study of a new notion of obfuscation, which we call bestpossible obfuscation. BestPossible ObfuscationBest possible obfuscation makes the relaxed requirement that the obfuscated program leaks as little information as any other program with the same functionality (and of similar size). In particular, this definition allows the program to leak non blackbox information. Bestpossible obfuscation guarantees that any information that is not hidden by the obfuscated program is also not hidden by any other similarsize program computing the same functionality, and thus the obfuscation is (literally) the best possible. We study bestpossible obfuscation and its relationship to previously studied definitions. Instead of requiring that an obfuscator strip a program of any non blackbox information, we require only that the (bestpossible) obfuscated program leak as little information as possible. Namely, the obfuscated program should be ``as private as'' any other program computing the same functionality (and of a certain size). A bestpossible obfuscator should transform any program so that anything that can be computed given access to the obfuscated program should also be computable from any other equivalent program (of some related size). A bestpossible obfuscation may leak non blackbox information (e.g. the code of a hardtolearn function), as long as whatever it leaks is efficiently learnable from any other similarsize circuit computing the same functionality. While this relaxed notion of obfuscation gives no absolute guarantee about what information is hidden in the obfuscated program, it does guarantee (literally) that the obfuscated code is the best possible. It is thus a meaningful notion of obfuscation, especially when we consider that programs are obfuscated every day in the real world without any provable security guarantee. Comparison with Previous DefinitionsWe study how bestpossible obfuscation relates to blackbox obfuscation. Bestpossible obfuscation is a relaxed requirement that departs from the blackbox paradigm of previous work. We first observe that any blackbox obfuscator is also a bestpossible obfuscator. Furthermore, we present a separation between the two notions of obfuscation. The separation result considers the complexity class of languages computable by polynomial sized ordered decision diagrams or POBDDs; these are logspace programs that can only read their input tape once, from left to right. We observe that any POBDD can be bestpossible obfuscated as a POBDD, whereas there are many natural functions computable by POBDDs that provably cannot be blackbox obfuscated as any POBDD. These two results give new possibility results (for bestpossible and indistinguishability obfuscation), and simple natural impossibility results (for blackbox obfuscation). Note that the impossibility result for blackbox obfuscation only applies when we restrict the representation of the obfuscator's output to be a POBDD itself. We also compare the notions of bestpossible and indistinguishability obfuscation. We show that any bestpossible obfuscator is also an indistinguishability obfuscator. For efficient obfuscators the definitions are equivalent. For inefficient obfuscation, the difference between the two definitions is sharp, as inefficient informationtheoretic indistinguishability obfuscators are easy to construct, but the existence of inefficient statistically bestpossible obfuscators even for the class of languages recognizable by 3CNF circuits implies that the polynomial hierarchy collapses to its second level. Hardness ResultsWe explore the limits of bestpossible obfuscation. We begin by considering informationtheoretically (statistically) bestpossible obfuscation, and show that if there exist (not necessarily efficient) statistically secure bestpossible obfuscators for the simple circuit family of 3CNF circuits, then the polynomial hierarchy collapses to its second level. We also consider bestpossible obfuscation in the (programmable) random oracle model. In this model, circuits can be built using special random oracle gates that compute a completely random function. Previously, this model was considered by Lynn, Prabhakaran and Sahai [3] as a promising setting for presenting positive results for obfuscation. We show that the random oracle can also be used to prove strong negative results for obfuscation, presenting a simple family of circuits with access to the random oracle, that are provably hard to be efficiently bestpossible obfuscated. This impossibility results extends to the blackbox and indistinguishability obfuscation notions. We note that using random oracles for obfuscation was originally motivated by the hope that giving circuits access to an idealized ``box'' computing a random function would make it easier to obfuscate more functionalities (and eventually perhaps the properties of the ``box'' could be realized by a software implementation). We, on the other hand, show that the existence of such boxes (or a software implementation with the idealized properties) could actually allow the construction of circuits that are impossible to obfuscate. Although this negative result does not rule out that every circuit without random oracle gates can be bestpossible obfuscated, we believe it is illuminating for two reasons. First, as a warning sign when considering obfuscation in the random oracle model, and secondly as its proof hints that achieving general purpose bestpossible obfuscation in the standard model would require a significant. Research SupportThis research was supported by NSF grant, CNS0430450, NSF grant CFF0635297 and a CymermanJakubskind award. References:[1] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit, Sahai, Salil P. Vadhan, Ke Yang. On the (Im)possibility of Obfuscating Programs. CRYPTO 2001: 118. [2] Shafi Goldwasser, Yael Tauman Kalai. On the Impossibility of Obfuscation with Auxiliary Input. FOCS 2005: 553562. [3] Ben Lynn, Manoj Prabhakaran, Amit Sahai. Positive Results and Techniques for Obfuscation. EUROCRYPT 2004: 2039. 

