International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Positive Results and Techniques for Obfuscation

Benjamin Lynn
Manoj Prabhakaran
Amit Sahai
Search ePrint
Search Google
Abstract: Informally, an obfuscator $\Obf$ is an efficient, probabilistic ``compiler'' that transforms a program $P$ into a new program $\Obf(P)$ with the same functionality as $P$, but such that $\Obf(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 [Barak et al]. 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 Barak et al. 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.
  title={Positive Results and Techniques for Obfuscation},
  booktitle={IACR Eprint archive},
  keywords={Obfuscation, Random Oracle, Access Control, Regular Expressions},
  note={Appears in Eurocrypt 2004 12476 received 22 Feb 2004, last revised 28 Feb 2004},
  author={Benjamin Lynn and Manoj Prabhakaran and Amit Sahai},