TY - CHAP

T1 - Positive results and techniques for obfuscation

AU - Lynn, Benjamin

AU - Prabhakaran, Manoj

AU - Sahai, Amit

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35048895442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=35048895442&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24676-3_2

DO - 10.1007/978-3-540-24676-3_2

M3 - Chapter

AN - SCOPUS:35048895442

SN - 3540219358

SN - 9783540219354

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 20

EP - 39

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Cachin, Christian

A2 - Camenisch, Jan

PB - Springer

ER -