On the (Im)possibility of Obfuscating Programs

DSpace/Manakin Repository

On the (Im)possibility of Obfuscating Programs

Citable link to this page


Title: On the (Im)possibility of Obfuscating Programs
Author: Goldreich, Oded; Vadhan, Salil; Barak, Boaz; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Yang, Ke

Note: Order does not necessarily reflect citation order of authors.

Citation: Barak, Boaz, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In Advances in Cryptology - CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 2001, Proceedings, ed. Joe Kilian, 1-18. Lecture Notes In Computer Science, 2139. Berlin: Springer, 2001.
Full Text & Related Files:
Abstract: Informally, an obfuscator O is an (efficient, probabilistic) "compiler" that takes as input a program (or circuit) P and produces a new program O(P) that has the same functionality as P yet is "unintelligible" in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are based on an interpretation of the "unintelligibility" condition in obfuscation as meaning that O(P) is a "virtual black box," in the sense that anything one can efficiently compute given O(P), one could also efficiently compute given oracle access to P.

In this work, we initiate a theoretical investigation of obfuscation. Our main result is that, even under very weak formalizations of the above intuition, obfuscation is impossible. We prove this by constructing a family of programs F that are unobfuscatable in the sense that (a) given any efficient program Pi that computes the same function as a program P\in F, the “source code” P can be efficiently reconstructed, yet (b) given oracle access to a (randomly selected) program P\in F, no efficient algorithm can reconstruct P (or even distinguish a certain bit in the code from random) except with negligible probability.

We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) only approximately preserve the functionality, and (c) only need to work for very restricted models of computation (TC_0). We also rule out several potential applications of obfuscators, by constructing “unobfuscatable” signature schemes, encryption schemes, and pseudorandom function families.
Published Version: http://dx.doi.org/10.1007/3-540-44647-8_1
Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2920191
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search