Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2139))
Included in the following conference series:
9197Accesses
Abstract
Informally, anobfuscator\( \mathcal{O} \) is an (efficient, probabilistic) “compiler” that takes as input a program (or circuit)P and produces a new program\( \mathcal{O} \)(P) that has the same functionality asP 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\( \mathcal{O} \) is a “virtual black box,” in the sense that anything one can efficiently compute given\( \mathcal{O} \), one could also efficiently compute given oracle access toP.
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 functions\( \mathcal{F} \) that areinherently unobfuscatable in the following sense: there is a property π:\( \mathcal{F} \) → {0,1} such that (a) givenany program that computes a functionf ∈\( \mathcal{F} \), the value π(f) can be efficiently computed, yet (b) givenoracle access to a (randomly selected) functionf ∈\( \mathcal{F} \), no efficient algorithm can compute π(f) much better than random guessing. We extend our impossibility result in a number of ways, including even obfuscators that (a) are not necessarily computable in polynomial time, (b) onlyapproximately 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. Technical report, Electronic Colloquium on Computational Complexity, 2001.http://www.eccc.uni-trier.de/eccc.
Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. InProceedings of the First Annual Conference on Computer and Communications Security. ACM, November 1993.
Dan Boneh and Richard Lipton. Algorithms for black-box fields and their applications to cryptography. In M. Wiener, editor,Advances in Cryptology—CRYPTO’ 96, volume 1109 ofLecture Notes in Computer Science, pages 283–297. Springer-Verlag, August 1996.
Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. InProceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 209–218, Dallas, 23–26 May 1998.
Christian Collberg and Clark Thomborson. Watermarking, tamperproofing, and obfuscation-tools for software protection. Technical Report TR00-03, The Department of Computer Science, University of Arizona, February 2000.
Danny Dolev, Cynthia Dwork, and Moni Naor. Nonmalleable cryptography.SIAM Journal on Computing, 30(2):391–437 (electronic), 2000.
Joan Feigenbaum and Michael Merritt, editors.Distributed computing and cryptography, Providence, RI, 1991. American Mathematical Society.
Amos Fiat and Adi Shamir. How to prove yourself: practical solutions to identification and signature problems. InAdvances in cryptology— CRYPTO’ 86 (Santa Barbara, Calif., 1986), pages 186–194. Springer, Berlin, 1987.
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions.Journal of the Association for Computing Machinery, 33(4):792–807, 1986.
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs.Journal of the ACM, 43(3):431–473, 1996.
Shafi Goldwasser and Silvio Micali. Probabilistic encryption.Journal of Computer and System Sciences, 28(2):270–299, April 1984.
Satoshi Hada. Zero-knowledge and code obfuscation. In T. Okamoto, editor,Advances in Cryptology-ASIACRYPT’ 2000, Lecture Notes in Computer Science, pages 443–457, Kyoto, Japan, 2000. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany.
Jonathan Katz and Moti Yung. Complete characterization of security notions for private-key encryption. InProceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 245–254, Portland, OR, May 2000. ACM.
David Naccache, Adi Shamir, and Julien P. Stern. How to copyright a function? In H. Imai and Y. Zheng, editors,Public Key Cryptography— PKC’ 99, volume 1560 ofLecture Notes in Computer Science, pages 188–196. Springer-Verlag, March 1999.
Moni Naor and Omer Reingold. Number-theoretic constructions of efficient pseudo-random functions. In38th Annual Symposium on Foundations of Computer Science, pages 458–467, Miami Beach, Florida, 20-22 October 1997. IEEE.
Ronald L. Rivest, Len Adleman, and Michael L. Dertouzos. On data banks and privacy homomorphisms. InFoundations of secure computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977), pages 169–179. Academic, New York, 1978.
Thomas Sander, Adam Young, and Moti Yung. Non-interactive cryptocomputing for NC1. In40th Annual Symposium on Foundations of Computer Science, pages 554–566, New York, NY, 17-19 October 1999. IEEE.
Frans van Dorsselaer. Obsolescent feature. Winning entry for the1998 International Obfuscated C Code Contest, 1998.http://www.ioccc.org/.
Author information
Authors and Affiliations
Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel
Boaz Barak & Oded Goldreich
Department of Computer Science and Engineering, University of California, San Diego, La Jolla, CA, 92093-0114
Rusell Impagliazzo
Computer Science Department, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA, 5213
Steven Rudich & Ke Yang
Department of Computer Science, Princeton University, 35 Olden St., Princeton, NJ, 08540
Amit Sahai
Division of Engineering and Applied Sciences, Harvard University, 33 Oxford Street, Cambridge, MA, 02138
Salil Vadhan
- Boaz Barak
You can also search for this author inPubMed Google Scholar
- Oded Goldreich
You can also search for this author inPubMed Google Scholar
- Rusell Impagliazzo
You can also search for this author inPubMed Google Scholar
- Steven Rudich
You can also search for this author inPubMed Google Scholar
- Amit Sahai
You can also search for this author inPubMed Google Scholar
- Salil Vadhan
You can also search for this author inPubMed Google Scholar
- Ke Yang
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
Yianilos Labs., 707 State Rd., Rt. 206, Suite 212, Princeton, NJ, 08540, USA
Joe Kilian
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Barak, B.et al. (2001). On the (Im)possibility of Obfuscating Programs. In: Kilian, J. (eds) Advances in Cryptology — CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science, vol 2139. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44647-8_1
Download citation
Published:
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-42456-7
Online ISBN:978-3-540-44647-7
eBook Packages:Springer Book Archive
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative