On Best-Possible Obfuscation
An obfuscator is a compiler that transforms any program (which we will view in this work as a boolean circuit) into an obfuscated program (also a circuit) that has the same input-output functionality as the original program, but is “unintelligible”. Obfuscation has applications for cryptography and...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag Berlin Heidelberg
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86876 https://orcid.org/0000-0003-4728-1535 |
| _version_ | 1826200156470509568 |
|---|---|
| author | Goldwasser, Shafi Rothblum, Guy N. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Goldwasser, Shafi Rothblum, Guy N. |
| author_sort | Goldwasser, Shafi |
| collection | MIT |
| description | An obfuscator is a compiler that transforms any program (which we will view in this work as a boolean circuit) into an obfuscated program (also a circuit) that has the same input-output functionality as the original program, but is “unintelligible”. Obfuscation has applications for cryptography and for software protection. Barak et al. (CRYPTO 2001, pp. 1–18, 2001) initiated a theoretical study of obfuscation, which focused on black-box obfuscation, where the obfuscated circuit should leak no information except for its (black-box) input-output functionality. A family of functionalities that cannot be obfuscated was demonstrated. Subsequent research has showed further negative results as well as positive results for obfuscating very specific families of circuits, all with respect to black box obfuscation. This work is a study of a new notion of obfuscation, which we call best-possible obfuscation. Best possible obfuscation makes the relaxed requirement that the obfuscated program leaks as little information as any other program with the same functionality (and of similar size). In particular, this definition allows the program to leak information that cannot be obtained from a black box. Best-possible obfuscation guarantees that any information that is not hidden by the obfuscated program is also not hidden by any other similar-size program computing the same functionality, and thus the obfuscation is (literally) the best possible. In this work we study best-possible obfuscation and its relationship to previously studied definitions. Our main results are: (1) A separation between black-box and best-possible obfuscation. We show a natural obfuscation task that can be achieved under the best-possible definition, but cannot be achieved under the black-box definition. (2) A hardness result for best-possible obfuscation, showing that strong (information-theoretic) best-possible obfuscation implies a collapse in the Polynomial-Time Hierarchy. (3) An impossibility result for efficient best-possible (and black-box) obfuscation in the presence of random oracles. This impossibility result uses a random oracle to construct hard-to-obfuscate circuits, and thus it does not imply impossibility in the standard model. |
| first_indexed | 2024-09-23T11:32:02Z |
| format | Article |
| id | mit-1721.1/86876 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:32:02Z |
| publishDate | 2014 |
| publisher | Springer-Verlag Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/868762022-10-01T04:13:48Z On Best-Possible Obfuscation Goldwasser, Shafi Rothblum, Guy N. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Goldwasser, Shafi An obfuscator is a compiler that transforms any program (which we will view in this work as a boolean circuit) into an obfuscated program (also a circuit) that has the same input-output functionality as the original program, but is “unintelligible”. Obfuscation has applications for cryptography and for software protection. Barak et al. (CRYPTO 2001, pp. 1–18, 2001) initiated a theoretical study of obfuscation, which focused on black-box obfuscation, where the obfuscated circuit should leak no information except for its (black-box) input-output functionality. A family of functionalities that cannot be obfuscated was demonstrated. Subsequent research has showed further negative results as well as positive results for obfuscating very specific families of circuits, all with respect to black box obfuscation. This work is a study of a new notion of obfuscation, which we call best-possible obfuscation. Best possible obfuscation makes the relaxed requirement that the obfuscated program leaks as little information as any other program with the same functionality (and of similar size). In particular, this definition allows the program to leak information that cannot be obtained from a black box. Best-possible obfuscation guarantees that any information that is not hidden by the obfuscated program is also not hidden by any other similar-size program computing the same functionality, and thus the obfuscation is (literally) the best possible. In this work we study best-possible obfuscation and its relationship to previously studied definitions. Our main results are: (1) A separation between black-box and best-possible obfuscation. We show a natural obfuscation task that can be achieved under the best-possible definition, but cannot be achieved under the black-box definition. (2) A hardness result for best-possible obfuscation, showing that strong (information-theoretic) best-possible obfuscation implies a collapse in the Polynomial-Time Hierarchy. (3) An impossibility result for efficient best-possible (and black-box) obfuscation in the presence of random oracles. This impossibility result uses a random oracle to construct hard-to-obfuscate circuits, and thus it does not imply impossibility in the standard model. National Science Foundation (U.S.) (NSF grant CFF-0635297) National Science Foundation (U.S.) (NSF grant CNS-0430450) Weitzmann Institute of Science (Cymerman-Jakubskind award) 2014-05-08T17:02:06Z 2014-05-08T17:02:06Z 2013-05 2007-07 Article http://purl.org/eprint/type/JournalArticle 0933-2790 1432-1378 http://hdl.handle.net/1721.1/86876 Goldwasser, Shafi, and Guy N. Rothblum. “On Best-Possible Obfuscation.” Journal of Cryptology (May 22, 2013). https://orcid.org/0000-0003-4728-1535 en_US http://dx.doi.org/10.1007/s00145-013-9151-z Journal of Cryptology Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag Berlin Heidelberg Other repository |
| spellingShingle | Goldwasser, Shafi Rothblum, Guy N. On Best-Possible Obfuscation |
| title | On Best-Possible Obfuscation |
| title_full | On Best-Possible Obfuscation |
| title_fullStr | On Best-Possible Obfuscation |
| title_full_unstemmed | On Best-Possible Obfuscation |
| title_short | On Best-Possible Obfuscation |
| title_sort | on best possible obfuscation |
| url | http://hdl.handle.net/1721.1/86876 https://orcid.org/0000-0003-4728-1535 |
| work_keys_str_mv | AT goldwassershafi onbestpossibleobfuscation AT rothblumguyn onbestpossibleobfuscation |