Show simple item record

dc.contributor.authorBarak, Boaz
dc.contributor.authorGoldreich, Oded
dc.contributor.authorImpagliazzo, Russell
dc.contributor.authorRudich, Steven
dc.contributor.authorSahai, Amit
dc.contributor.authorVadhan, Salil P.
dc.contributor.authorYang, Ke
dc.date.accessioned2014-08-05T14:51:03Z
dc.date.issued2012
dc.identifier.citationBarak, Boaz, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. 2012. On the (Im)possibility of Obfuscating Programs. Journal of the ACM 59, no. 2: 1–48.en_US
dc.identifier.issn0004-5411en_US
dc.identifier.urihttp://nrs.harvard.edu/urn-3:HUL.InstRepos:12644697
dc.description.abstractInformally, 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.en_US
dc.description.sponsorshipEngineering and Applied Sciencesen_US
dc.language.isoen_USen_US
dc.publisherAssociation for Computing Machinery (ACM)en_US
dc.relation.isversionofdoi:10.1145/2160158.2160159en_US
dash.licenseOAP
dc.subjectcomplexity theoryen_US
dc.subjectcryptographyen_US
dc.subjecthomomorphic encryptionen_US
dc.subjectpseudorandom functionsen_US
dc.subjectRice’s Theoremen_US
dc.subjectsoftware protectionen_US
dc.subjectsoftware watermarkingen_US
dc.subjectstatistical zero knowledgeen_US
dc.titleOn the (Im)possibility of Obfuscating Programsen_US
dc.typeJournal Articleen_US
dc.description.versionAccepted Manuscripten_US
dc.relation.journalJournal of the ACMen_US
dash.depositing.authorVadhan, Salil P.
dc.date.available2014-08-05T14:51:03Z
dc.identifier.doi10.1145/2160158.2160159*
workflow.legacycommentsFAR 2013; this is NOT a duplicate, but rather a journal publication with the same name as a conference paperen_US
dash.contributor.affiliatedVadhan, Salil


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record