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.
Category / Keywords: Obfuscation, Random Oracle, Access Control, Regular Expressions Publication Info: Appears in Eurocrypt 2004 Date: received 22 Feb 2004, last revised 28 Feb 2004 Contact author: mp at princeton edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20040228:141917 (All versions of this report) Discussion forum: Show discussion | Start new discussion