articleJournal of the ACMApr 1, 2012Closed access

On the (im)possibility of obfuscating programs

BBBoaz BarakOGOded GoldreichRIRussell ImpagliazzoSRSteven RudichASAmit Sahai

Microsoft (United States) · Microsoft Research New England (United States) · +6 more institutions

Indexed incrossref

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…

Citation impact

599
total citations
FWCI
86.20
Percentile
100%
References
56
Citations per year

Authors

7

Topics & keywords

Topics
Keywords
  • Obfuscation
  • Computer science
  • Impossibility
  • Theoretical computer science
  • Random oracle
  • Oracle
  • Homomorphic encryption
  • Cryptography
No related works found for this paper.

Funding