Positive results and techniques for obfuscation

Benjamin Lynn, Manoj Prabhakaran, Amit Sahai

Research output: Chapter in Book/Report/Conference proceedingChapter


Informally, an obfuscator O is an efficient, probabilistic "compiler" that transforms a program P into a new program O(P) with the same functionality as P, but such that O(P) protects any secrets that may be built into and used by P. Program obfuscation, if possible, would have numerous important cryptographic applications, including: (1) "Intellectual property" protection of secret algorithms and keys in software, (2) Solving the long-standing open problem of homomorphic public-key encryption, (3) Controlled delegation of authority and access, (4) Transforming Private-Key Encryption into Public-Key Encryption, and (5) Access Control Systems. Unfortunately however, program obfuscators that work on arbitrary programs cannot exist [1]. No positive results for program obfuscation were known prior to this work. In this paper, we provide the first positive results in program obfuscation. We focus on the goal of access control, and give several provable obfuscations for complex access control functionalities, in the random oracle model. Our results are obtained through non-trivial compositions of obfuscations; we note that general composition of obfuscations is impossible, and so developing techniques for composing obfuscations is an important goal. Our work can also be seen as making initial progress toward the goal of obfuscating finite automata or regular expressions, an important general class of machines which are not ruled out by the impossibility results of [1]. We also note that our work provides the first formal proof techniques for obfuscation, which we expect to be useful in future work in this area.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsChristian Cachin, Jan Camenisch
Number of pages20
ISBN (Print)3540219358, 9783540219354
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Positive results and techniques for obfuscation'. Together they form a unique fingerprint.

Cite this