On the (im)possibility of obfuscating programs

By Boaz Barak, Oded Goldreich, Russell Impagliazzo, S. Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang. 2001

1,515 citations recorded by the source corpus.

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 (TC0). We also rule out several potential applications of obfuscators, by constructing “unobfuscatable” signature schemes, encryption schemes, and pseudorandom function families.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, background): “However, making the database accessible by more than a single client under existing CPIR preprocessing schemes requires prohibitively expensive cryptography (a virtual black-box obfuscation primitive [10] instantiated from indistinguishability obfuscation [38]).”
On the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy (2010, background): “A basic impossibility result of Barak et al [6] says that some functions cannot be obfuscated.”
Multi-Input Functional Encryption (2014, background): “– In the setting where the adversary receives only a single key for a 2-ary function, and receives one evaluation key and one challenge ciphertext, if simulation security is possible then virtual black-box obfuscation must be possible for arbitrary circuits, which is known to be impossible [2].”
Pseudorandom Functions: Three Decades Later (2017, background): “Definition 22 (Indistinguishability obfuscation [19]).”
Towards Better Program Obfuscation: Optimization via Language Models (2016, background): “Although no obfuscation is perfect [6, 13] , we can leverage it to deter reverse engineering and make software analyses (such as abstract interpretation [9]) imprecise [10, 12, 11].”
High Accuracy and High Fidelity Extraction of Neural Networks (2019, background): “One unrealized approach is obfuscation [56], where an equivalent program could be released and queried as”
Obfuscator-LLVM -- Software Protection for the Masses (2015, background): “He can thus read data in memory, including sensitive values such as cryptographic keys, or modify any intermediate values during the software execution and consequently analyze any piece of software with the goal of, e.g., understanding and illegally copying it.”
Learning to Protect Communications with Adversarial Neural Cryptography (2016, background): “We therefore believe that the most likely explanation for this successful training run was that Alice and Bob accidentally obtained some “security by obscurity” (cf. the derivation of asymmetric schemes from symmetric schemes by obfuscation (Barak et al., 2012)).”
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers (2010, background): “’s result that there is no general obfuscator [7] .”
Turning Your Weakness Into a Strength: Watermarking Deep Neural Networks by Backdooring (2018, background): “The terminology and definitions are inspired by [7, 24].”
HOP: Hardware makes Obfuscation Practical (2017, background): “First, it is wellunderstood that strong (simulation secure) notions of program obfuscation cannot be realized in general [4] — although they are desired or necessary in many applications such as the aforementioned ones.”
Theory of Cryptography (2014, methodology): “We start by recalling the syntax and functionality requirement for circuit obfuscation as defined in [3].”
Counterfeit Integrated Circuits: A Rising Threat in the Global Semiconductor Supply Chain (2014, neutral): “[78] B.”
Recovering clear, natural identifiers from obfuscated JS names (2017, background): “Karaivanov et al. [24], as did Nguyen et al. [33], experimented with translation from C# to Java on a parallel corpus of around 20,000 C#-to-Java method translations mined from open-source projects available However, they also trained hybrid phrase and rule-based SMT models that take the grammatical”