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 efficient programs P that are unobfuscatable in the sense that (a) given any efficient program P that computes the same function as a program P ∈ P, the "source code" P can be efficiently reconstructed, yet (b) given oracle access to a (randomly selected) program P ∈ P, 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. In this work, we initiate a theoretical investigation of obfuscation. We examine various formalizations of the notion, in an attempt to understand what we can and cannot hope to achieve. Our main result is a negative one, showing that obfuscation (as it is typically understood) is impossible. Before describing this result and others in more detail, we outline some of the potential applications of obfuscators, both for motivation and to clarify the notion. Software Protection.. The most direct applications of obfuscators are for various forms of software protection. By definition, obfuscating a program protects it against reverse engineering. For example, if one party, Alice, discovers a more efficient algorithm for factoring integers, she may wish to sell another party, Bob, a program for apparently weaker tasks (such as breaking the RSA cryptosystem) that use the factoring algorithm as a subroutine without actually giving Bob a factoring algorithm. Alice could hope to achieve this by obfuscating the program she gives to Bob. Intuitively, obfuscators would also be useful in watermarking software (cf., [CT; NSS]). A software vendor could modify a program's behavior in a way that uniquely identifies the person to whom it is sold, and then obfuscate the program to guarantee that this "watermark" is difficult to remove. Removing Random Oracles.. The Random Oracle Model [BR] is an idealized cryptographic setting in which all parties have access to a truly random function. It is (heuristically) hoped that protocols designed in this model will remain secure when implemented using an efficient, publicly computable cryptographic hash function in place of the random function. While it is known that this is not true in general [CGH], it is unknown whether there exist efficiently computable functions with strong enough properties to be securely used in place of the random function in various specific protocols 2 . One might hope to obtain such functions by obfuscating a family of pseudorandom functions [GGM], whose input-output behavior is by definition indistinguishable from that of a truly random function. Transforming Private-Key Encryption into Public-Key Encryption.. Obfuscation can also be used to create new public-key encryption schemes by obfuscating a privatekey encryption scheme. Given a secret key K of a private-key encryption scheme, one can publish an obfuscation of the encryption algorithm Enc K . This allows everyone to encrypt, yet only one possessing the secret key K should be able to decrypt. Interestingly, in the original paper of Diffie and Hellman [DH], the above was the reason given to believe that public-key cryptosystems might exist even though there were no candidates known yet. That is, they suggested that it might be possible to obfuscate a private-key encryption scheme. 3 2 We note that the results of [CGH] can also be seen as ruling out a very strong "virtual black box" definition of obfuscators. This is because their result implies that no obfuscator applied to any pseudorandom function family could work for all protocols, while a very strong virtual black box definition would guarantee this. We note, however, that our main results rule out a seemingly much weaker definition of obfuscation. Also, we note that ruling out strong virtual black box definitions is almost immediate: For example, one thing that can be efficiently computed from O(P ) is the program O(P ) itself. However, for any program P corresponding to a function that is hard to learn from queries, it would be infeasible to produce any program equivalent to P in functionality given only oracle access to P . 3 From [DH]: "A more practical approach to finding a pair of easily computed inverse algorithms E and D; such that D is hard to infer from E, makes use of the difficulty of analyzing programs in low level languages. Anyone who has tried to determine what operation is accomplished by someone else's machine language program knows that E itself (i.e., what E does) can be hard to infer from an algorithm for E. If the program were to be made purposefully confusing through the addition of unneeded variables and statements, then Impossibility of Applications.. To give further evidence that our impossibility result is not an artifact of definitional choices, but rather is inherent in the "virtual black box" determining an inverse algorithm could be made very difficult. Of course, E must be complicated enough to prevent its identification from input-output pairs. Essentially what is required is a one-way compiler: one that takes an easily understood program written in a high level language and translates it into an incomprehensible program in some machine language. The compiler is one-way because it must be feasible to do the compilation, but infeasible to reverse the process. Since efficiency in size of program and run time are not crucial in this application, such compilers may be possible if the structure of the machine language can be optimized to assist in the confusion." A:5 idea, we also demonstrate that several of the applications of obfuscators are impossible. We do this by constructing unobfuscatable signature schemes, encryption schemes, and pseudorandom functions. These are objects satisfying the standard definitions of security, but for which one can efficiently compute the secret key K from any program that signs (or encrypts or evaluates the pseudorandom function, resp.) relative to K. Hence handing out "obfuscated forms" of these keyed-algorithms is highly insecure. In particular, we complement Canetti et. al.'s critique of the Random Oracle Methodology [CGH]. They show that there exist (contrived) protocols that are secure in the idealized Random Oracle Model (of [BR]), but are insecure when the random oracle is replaced with any (efficiently computable) function. Our results imply that for even for natural protocols that are secure in the random oracle model, (e.g., Fiat-Shamir type schemes [FS]), there exist (contrived) pseudorandom functions, such that these protocols are insecure when the random oracle is replaced with any program that computes the (contrived) pseudorandom function. We mention that, subsequent to our work, Barak [Bar1] constructed arguably natural protocols that are secure in the random oracle model (e.g. those obtained by applying the Fiat-Shamir heuristic [FS] to his public-coin zero-knowledge arguments) but are insecure when the random oracle is replaced by any efficiently computable function. Definition 2.1 (TM obfuscator). A probabilistic algorithm O is a TM obfuscator for the collection F of Turing machines if the following three conditions hold: 5 See Footnote 7.
Unfortunately, obfuscating a program is considered a weak form of protection, as shown by Barak et al. REF .
On the (Im)possibility of Obfuscating Programs
IACR Cryptology ePrint Archive
IACR Cryptology ePrint Archive
Computer Science