Abstract
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. 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 non black-box information. 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.
-
1
A hardness result for best-possible obfuscation, showing that strong (information-theoretic) best-possible obfuscation implies a collapse in the polynomial hierarchy.
-
1
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.
Chapter PDF
Similar content being viewed by others
References
Aiello, W., Håstad, J.: Statistical Zero-Knowledge Languages can be Recognized in Two Rounds. Journal of Computer and System Sciences 42(3), 327–345 (1991)
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S P, Yang, K.: On the (Im)possibility of Obfuscating Programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73. ACM Press, New York (1993)
Boppana, R B, Håstad, J., Zachos, S.: Does co-NP Have Short Interactive Proofs? Information Processing Letters 25(2), 127–132 (1987)
Bryant, R E.: Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers C(35), No. 8, 677-691 (August 1986)
Canetti, R.: Towards Realizing Random Oracles: Hash Functions That Hide All Partial Information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455–469. Springer, Heidelberg (1997)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM 51(4), 557–594 (2004)
Canetti, R., Micciancio, D., Reingold, O.: Perfectly One-Way Probabilistic Hash Functions (Preliminary Version). In: STOC, pp. 131–140 (1998)
Dodis, Y., Smith, A.: Correcting errors without leaking partial information. In: STOC, pp. 654–663 (2005)
Fortnow, L.: The complexity of perfect zero-knowledge. Advances in Computing Research 5, 327–343 (1989)
Goldwasser, S., Tauman Kalai, Y.: On the (In)security of the Fiat-Shamir Paradigm. In: FOCS, pp. 102–113 (2003)
Goldwasser, S., Tauman Kalai, Y.: On the Impossibility of Obfuscation with Auxiliary Input. In: FOCS, pp. 553–562 (2005)
Goldwasser, S., Micali, S.: Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. In: STOC, pp. 365–377 (1982)
Feigenbaum, J., Fortnow, L.: Random-Self-Reducibility of Complete Sets. SIAM Journal on Computing 22(5), 994–1005 (1993)
Fiat, A., Shamir, A.: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)
Narayanan, A., Shmatikov, V.: Obfuscated databases and group privacy. In: ACM Conference on Computer and Communications Security, pp. 102–111. ACM Press, New York (2005)
Lynn, B., Prabhakaran, M., Sahai, A.: Positive Results and Techniques for Obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004)
Malkin, T.: Personal Communication (2006)
Okamoto, T.: On Relationships between Statistical Zero-Knowledge Proofs. Journal of Computer and System Sciences 60(1), 47–108 (2000)
Sahai, A., Vadhan, S.P.: A complete problem for statistical zero knowledge. Journal of the ACM 50(2), 196–249 (2003)
Wee, H.: On obfuscating point functions. In: STOC, pp. 523–532 (2005)
Yao, A.C.-C.: Theory and Applications of Trapdoor Functions (Extended Abstract). In: FOCS, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Goldwasser, S., Rothblum, G.N. (2007). On Best-Possible Obfuscation. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-70936-7_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70935-0
Online ISBN: 978-3-540-70936-7
eBook Packages: Computer ScienceComputer Science (R0)