### On the (im)possibility of obfuscating programsOn the (im)possibility of obfuscating programs

Access Restriction
Subscribed

 Author Barak, Boaz ♦ Goldreich, Oded ♦ Impagliazzo, Russell ♦ Rudich, Steven ♦ Sahai, Amit ♦ Vadhan, Salil ♦ Yang, Ke Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2012 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Complexity theory ♦ Rice's Theorem ♦ Cryptography ♦ Homomorphic encryption ♦ Pseudorandom functions ♦ Software protection ♦ Software watermarking ♦ Statistical zero knowledge Abstract Informally, an $\textit{obfuscator}$ $\textit{O}$ is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit) $\textit{P}$ and produces a new program $\textit{O}(\textit{P})$ that has the same functionality as $\textit{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 $\textit{O}(\textit{P})$ is a “virtual black box,” in the sense that anything one can efficiently compute given $\textit{O}(\textit{P}),$ one could also efficiently compute given oracle access to $\textit{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 $\textit{P}$ that are $\textit{unobfuscatable}$ in the sense that (a) given $\textit{any}$ efficient program $\textit{P}'$ that computes the same function as a program $\textit{P}$ ∈ $\textit{p},$ the “source code” $\textit{P}$ can be efficiently reconstructed, yet (b) given oracle access to a (randomly selected) program $\textit{P}$ ∈ $\textit{p},$ no efficient algorithm can reconstruct $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2012-05-03 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 59 Issue Number 2 Page Count 48 Starting Page 1 Ending Page 48

#### Open content in new tab

Source: ACM Digital Library