Research Abstracts - 2007

On Best-Possible Obfuscation

Shafi Goldwasser & Guy N. Rothblum

Overview

An 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 input-output 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 black-box obfuscation, where the obfuscated circuit should leak no information except for its (black-box) input-output 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 best-possible obfuscation.

Best-Possible Obfuscation

Best 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 black-box information. Best-possible obfuscation guarantees that any information that is not hidden by the obfuscated program is also not hidden by any other similar-size program computing the same functionality, and thus the obfuscation is (literally) the best possible. We study best-possible obfuscation and its relationship to previously studied definitions.

Instead of requiring that an obfuscator strip a program of any non black-box information, we require only that the (best-possible) 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 best-possible 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 best-possible obfuscation may leak non black-box information (e.g. the code of a hard-to-learn function), as long as whatever it leaks is efficiently learnable from any other similar-size 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 Definitions

We study how best-possible obfuscation relates to black-box obfuscation. Best-possible obfuscation is a relaxed requirement that departs from

the black-box paradigm of previous work. We first observe that any black-box obfuscator is also a best-possible 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 log-space programs that can only read their input tape once, from left to right. We observe that any POBDD can be best-possible obfuscated as a POBDD, whereas there are many natural functions computable by POBDDs that provably cannot be black-box obfuscated as any POBDD. These two results give new possibility results (for best-possible and indistinguishability obfuscation), and simple natural impossibility results (for black-box obfuscation). Note that the impossibility result for black-box obfuscation only applies when we restrict the representation of the obfuscator's output to be a POBDD itself.

We also compare the notions of best-possible and indistinguishability obfuscation. We show that any best-possible 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 information-theoretic indistinguishability obfuscators are easy to construct, but the existence of inefficient statistically best-possible obfuscators even for the class of languages recognizable by 3-CNF circuits implies that the polynomial hierarchy collapses to its second level.

Hardness Results

We explore the limits of best-possible obfuscation. We begin by considering information-theoretically (statistically) best-possible obfuscation, and show that if there exist (not necessarily efficient) statistically secure best-possible obfuscators for the simple circuit family of 3-CNF circuits, then the polynomial hierarchy collapses to its second level.

We also consider best-possible 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 best-possible obfuscated. This impossibility results extends to the black-box 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 best-possible 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 best-possible obfuscation in the standard model would require a significant.

Research Support

This research was supported by NSF grant, CNS-0430450, NSF grant CFF-0635297 and a Cymerman-Jakubskind 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: 1-18.

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

[3] Ben Lynn, Manoj Prabhakaran, Amit Sahai. Positive Results and Techniques for Obfuscation. EUROCRYPT 2004: 20-39.