[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

On the (im)possibility of obfuscating programs

Published: 03 May 2012 Publication History

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 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 Pp, the “source code” P can be efficiently reconstructed, yet (b) given oracle access to a (randomly selected) program Pp, 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.

Supplementary Material

Auxiliary material (a6-barak-auxiliarylink.html)
Link to an informal essay about obfuscation impossibility (unrefereed material)

References

[1]
Barak, B. 2001. How to go beyond the black-box simulation barrier. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. IEEE Computer Soc., Los Alamitos, CA, 106--115.
[2]
Barak, B. 2002. Can we obfuscate programs? http://www.cs.princeton.edu/∼boaz/Papers/obf_informal.html.
[3]
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., and Yang, K. 2001. On the (im)possibility of obfuscating programs. In Advances in Cryptology—CRYPTO '01. J. Kilian, Ed., Lecture Notes in Computer Science Series, vol. 2139, Springer-Verlag, 1--18.
[4]
Bellare, M. and Rogaway, P. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st Annual Conference on Computer and Communications Security. ACM.
[5]
Boneh, D. and Lipton, R. 1996. Algorithms for black-box fields and their applications to cryptography. In Advances in Cryptology—CRYPTO '96. M. Wiener, Ed., Lecture Notes in Computer Science Series, vol. 1109, Springer-Verlag, 283--297.
[6]
Borchert, B. and Stephan, F. 2000. Looking for an analogue of Rice's theorem in circuit complexity theory. Math. Logic Quart. 46, 4, 489--504.
[7]
Canetti, R. 1997. Towards realizing random oracles: Hash functions that hide all partial information. In Advances in Cryptology CRYPTO, Lecture Notes in Computer Science Series, vol. 1294, Springer, 455--469.
[8]
Canetti, R., Goldreich, O., and Halevi, S. 1998a. The random oracle methodology, revisited. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. 209--218.
[9]
Canetti, R., Micciancio, D., and Reingold, O. 1998b. Perfectly one-way probabilistic hash functions. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing. 131--140.
[10]
Collberg, C. and Thomborson, C. 2000. Watermarking, tamper-proofing, and obfuscation--tools for software protection. Tech. rep. TR00-03, Department of Computer Science, University of Arizona.
[11]
De Santis, A., Di Crescenzo, G., Persiano, G., and Yung, M. 1998. Image Density is complete for non-interactive-SZK. In Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science. Springer-Verlag, 784--795.
[12]
Diffie, W. and Hellman, M. E. 1976. New directions in cryptography. IEEE Trans. Inf. Theory 22, 6, 644--654.
[13]
Dodis, Y. and Smith, A. 2005. Correcting errors without leaking partial information. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing. 654--663.
[14]
Dolev, D., Dwork, C., and Naor, M. 2000. Nonmalleable cryptography. SIAM J. Comput. 30, 2, 391--437.
[15]
Dwork, C., Naor, M., Reingold, O., and Stockmeyer, L. J. 2003. Magic functions. J. ACM 50, 6, 852--921.
[16]
Even, S., Selman, A. L., and Yacobi, Y. 1984. The complexity of promise problems with applications to public-key cryptography. Inf. Cont. 61, 2, 159--173.
[17]
Feigenbaum, J. and Merritt, M., Eds. 1991. Distributed Computing and Cryptography. American Mathematical Society, Providence, RI.
[18]
Fiat, A. and Shamir, A. 1987. How to prove yourself: practical solutions to identification and signature problems. In Advances in Cryptology—CRYPTO '86. Springer, Berlin, 186--194.
[19]
Gennaro, R. and Trevisan, L. 2000. Lower bounds on the efficiency of generic cryptographic constructions. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE.
[20]
Goldreich, O. 2001. Foundations of Cryptography. Cambridge University Press, Cambridge, UK.
[21]
Goldreich, O. 2004. Foundations of Cryptography. II. Cambridge University Press, Cambridge, UK.
[22]
Goldreich, O., Goldwasser, S., and Micali, S. 1986. How to construct random functions. J. ACM 33, 4, 792--807.
[23]
Goldreich, O. and Ostrovsky, R. 1996. Software protection and simulation on oblivious RAMs. J. ACM 43, 3, 431--473.
[24]
Goldreich, O., Sahai, A., and Vadhan, S. 1999. Can statistical zero-knowledge be made non-interactive?, or On the relationship of SZK and NISZK. In Advances in Cryptology—CRYPTO '99. Lecture Notes in Computer Science, vol. 1666, Springer-Verlag, 467--484.
[25]
Goldwasser, S. and Kalai, Y. T. 2005. On the impossibility of obfuscation with auxiliary input. In Proceedings of the Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 553--562.
[26]
Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270--299.
[27]
Goldwasser, S. and Rothblum, G. N. 2007. On best-possible obfuscation. In Proceedings of the 4th Conference on Theory of Cryptography (TCC '07). 194--213.
[28]
Hada, S. 2000. Zero-knowledge and code obfuscation. In Advances in Cryptology—ASIACRYPT '00, T. Okamoto, Ed., Lecture Notes in Computer Science, 443--457.
[29]
Håstad, J., Impagliazzo, R., Levin, L. A., and Luby, M. 1999. A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 4, 1364--1396.
[30]
Hemaspaandra, L. A. and Rothe, J. 2000. A second step towards complexity-theoretic analogs of rice's theorem. Theoreti. Comput. Sci. 244, 1--2, 205--217.
[31]
Hemaspaandra, L. A. and Thakur, M. 2004. Lower bounds and the hardness of counting properties. Theoret. Comput. Sci. 326, 1-3, 1--28.
[32]
Hofheinz, D., Malone-Lee, J., and Stam, M. 2007. Obfuscation for cryptographic purposes. In Proceedings of the 4th Conference on Theory of Cryptography (TCC '07). 214--232.
[33]
Hohenberger, S., Rothblum, G. N., Shelat, A., and Vaikuntanathan, V. 2007. Securely obfuscating re-encryption. In Proceedings of the 4th Conference on Theory of Cryptography (TCC '07). 233--252.
[34]
Impagliazzo, R. and Luby, M. 1989. One-way functions are essential for complexity based cryptography (extended abstract). In Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE, 230--235.
[35]
Katz, J. and Yung, M. 2000. Complete characterization of security notions for private-key encryption. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. ACM, 245--254.
[36]
Kearns, M. J. and Vazirani, U. V. 1994. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA.
[37]
Luby, M. and Rackoff, C. 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17, 2, (Special issue on cryptography.) 373--386.
[38]
Lynn, B., Prabhakaran, M., and Sahai, A. 2004. Positive results and techniques for obfuscation. In EUROCRYPT, C. Cachin and J. Camenisch, Eds., Lecture Notes in Computer Science Series, vol. 3027, Springer, 20--39.
[39]
Matheson, L. R., Mitchell, S. G., Shamoon, T. G., Tarjan, R. E., and Zane, F. 1998. Robustness and security of digital watermarks. In Proceedings of the Symposium on Financial Cryptography—FC '98, H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science Series, vol. 1465, Springer, 227--240.
[40]
Naccache, D., Shamir, A., and Stern, J. P. 1999. How to copyright a function? In Proceedings of the Symposium on Public Key Cryptography—PKC '99. H. Imai and Y. Zheng, Eds., Lecture Notes in Computer Science Series, vol. 1560, Springer-Verlag, 188--196.
[41]
Naor, M. and Reingold, O. 1997. Number-theoretic constructions of efficient pseudo-random functions. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science. IEEE, 458--467.
[42]
Narayanan, A. and Shmatikov, V. 2005. Obfuscated databases and group privacy. In Proceedings of the ACM Conference on Computer and Communications Security, V. Atluri, C. Meadows, and A. Juels, Eds., ACM, 102--111.
[43]
Narayanan, A. and Shmatikov, V. 2006. On the limits of point function obfuscation. Cryptology ePrint Archive, Report 2006/182. http://eprint.iacr.org/.
[44]
Petitcolas, F. A. P., Anderson, R. J., and Kuhn, M. J. 1999. Information hiding—a survey. Proc. IEEE 87, 7, 1062--1078.
[45]
Rivest, R. L., Adleman, L., and Dertouzos, M. L. 1978. On data banks and privacy homomorphisms. In Proceedings of the Foundations of Secure Computation. Academic Press, New York, 169--179.
[46]
Sahai, A. and Vadhan, S. 2003. A complete problem for statistical zero knowledge. J. ACM 50, 2, 196--249.
[47]
Sander, T., Young, A., and Yung, M. 1999. Non-interactive cryptocomputing for NC1. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. IEEE, New York, NY, 554--566.
[48]
Sipser, M. 2005. Introduction to the Theory of Computation 2nd Ed. Course Technology.
[49]
van Dorsselaer, F. 1998. Obsolescent feature. Winning entry for the 1998 International Obfuscated C Code Contest. http://www.ioccc.org/.
[50]
Wee, H. 2005. On obfuscating point functions. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 523--532.

Cited By

View all
  • (2025)Code Obfuscation: A Comprehensive Approach to Detection, Classification, and Ethical ChallengesAlgorithms10.3390/a1802005418:2(54)Online publication date: 21-Jan-2025
  • (2024)Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom GeneratorsIACR Communications in Cryptology10.62056/aevur-10kOnline publication date: 8-Jul-2024
  • (2024)Privacy-preserving machine learning with tensor networksQuantum10.22331/q-2024-07-25-14258(1425)Online publication date: 25-Jul-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM
Journal of the ACM  Volume 59, Issue 2
April 2012
175 pages
ISSN:0004-5411
EISSN:1557-735X
DOI:10.1145/2160158
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2012
Accepted: 01 October 2011
Revised: 01 July 2010
Received: 01 January 2008
Published in JACM Volume 59, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Complexity theory
  2. Rice's Theorem
  3. cryptography
  4. homomorphic encryption
  5. pseudorandom functions
  6. software protection
  7. software watermarking
  8. statistical zero knowledge

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)153
  • Downloads (Last 6 weeks)14
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2025)Code Obfuscation: A Comprehensive Approach to Detection, Classification, and Ethical ChallengesAlgorithms10.3390/a1802005418:2(54)Online publication date: 21-Jan-2025
  • (2024)Simple Watermarking Pseudorandom Functions from Extractable Pseudorandom GeneratorsIACR Communications in Cryptology10.62056/aevur-10kOnline publication date: 8-Jul-2024
  • (2024)Privacy-preserving machine learning with tensor networksQuantum10.22331/q-2024-07-25-14258(1425)Online publication date: 25-Jul-2024
  • (2024)A Method to Quantitative Compare Obfuscating TtransformationsСпособ количественного сравнения обфусцирующих преобразованийInformatics and AutomationИнформатика и автоматизация10.15622/ia.23.3.323:3(684-726)Online publication date: 28-May-2024
  • (2024)Quantum State Obfuscation from Classical OraclesProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649673(1009-1017)Online publication date: 10-Jun-2024
  • (2024)Obfuscating Verifiable Random Functions for Proof-of-Stake BlockchainsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.332105121:4(2982-2996)Online publication date: 1-Jul-2024
  • (2024)Provably-Secure One-Message Unilateral Entity Authentication SchemesIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.328847321:4(1665-1679)Online publication date: 1-Jul-2024
  • (2024)Homomorphic multi-party computation for Internet of Medical ThingsPeer-to-Peer Networking and Applications10.1007/s12083-024-01805-917:6(4049-4069)Online publication date: 12-Sep-2024
  • (2024)Watermarking PRFs and PKE Against Quantum AdversariesJournal of Cryptology10.1007/s00145-024-09500-x37:3Online publication date: 26-Apr-2024
  • (2024)Quantum Point ObfuscationQuantum Nonlinear Function Obfuscation Theory and Application10.1007/978-981-97-6722-9_3(31-49)Online publication date: 16-Oct-2024
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media