Abstract
Loosely speaking, an obfuscation O of a function f should satisfy two requirements: firstly, using O, it should be possible to evaluate f; secondly, O should not reveal anything about f that cannot be learnt from oracle access to f alone. Several definitions for obfuscation exist. However, most of them are very hard to satisfy, even when focusing on specific applications such as obfuscating a point function (e.g., for authentication purposes).
In this work, we propose and investigate two new variants of obfuscation definitions. Our definitions are simulation-based (i.e., require the existence of a simulator that can efficiently generate fake obfuscations) and demand only security on average (over the choice of the obfuscated function). We stress that our notions are not free from generic impossibilities: there exist natural classes of function families that cannot be securely obfuscated. Hence we cannot hope for a general-purpose obfuscator with respect to our definition. However, we prove that there also exist several natural classes of functions for which our definitions yield interesting results.
Specifically, we show that our definitions have the following properties:
- Usefulness: :
-
Securely obfuscating (the encryption function of) a secure private-key encryption scheme yields a secure public-key encryption scheme.
- Achievability: :
-
There exist obfuscatable private-key encryption schemes. Also, a point function chosen uniformly at random can easily be obfuscated with respect to the weaker one (but not the stronger one) of our definitions. (Previous work focused on obfuscating point functions from arbitrary distributions.)
- Generic impossibilities: :
-
There exist unobfuscatable private-key encryption schemes. Furthermore, pseudorandom functions cannot be obfuscated with respect to our definitions.
Our results show that, while it is hard to avoid generic impossibilities, useful and reasonable obfuscation definitions are possible when considering specific tasks (i.e., function families).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B. Adida, D. Wikström, How to shuffle in public, in TCC 2007, ed. by S.P. Vadhan. Amsterdam, The Netherlands, February 21–24, 2007. LNCS, vol. 4392 (Springer, Berlin, 2007), pp. 555–574
M. Backes, B. Pfitzmann, M. Waidner, A composable cryptographic library with nested operations, in ACM CCS 03, ed. by S. Jajodia, V. Atluri, T. Jaeger. Washington DC, USA, October 27–30, 2003 (ACM Press, New York, 2003), pp. 220–230
B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang, On the (im)possibility of obfuscating programs, in CRYPTO 2001, ed. by J. Kilian. Santa Barbara, CA, USA, August 19–23, 2001. LNCS, vol. 2139 (Springer, Berlin, 2001), pp. 1–18
D. Beaver, Foundations of secure interactive computing, in CRYPTO’91, ed. by J. Feigenbaum. Santa Barbara, CA, USA, August 11–15, 1992. LNCS, vol. 576 (Springer, Berlin, 1992), pp. 377–391
M. Bellare, C. Namprempre, Authenticated encryption: Relations among notions and analysis of the generic composition paradigm, in ASIACRYPT 2000, ed. by T. Okamoto. Kyoto, Japan, December 3–7, 2000. LNCS, vol. 1976 (Springer, Berlin, 2000), pp. 531–545
M. Bellare, A. Desai, E. Jokipii, P. Rogaway, A concrete security treatment of symmetric encryption, in 38th FOCS. Miami Beach, Florida, October 19–22, 1997 (IEEE Computer Society, Los Alamitos, 1997), pp. 394–403
M. Bellare, A. Boldyreva, A. O’Neill, Deterministic and efficiently searchable encryption, in CRYPTO 2007, ed. by A. Menezes. Santa Barbara, CA, USA, August 19–23, 2007. LNCS, vol. 4622 (Springer, Berlin, 2007), pp. 535–552
R. Canetti, Towards realizing random oracles: Hash functions that hide all partial information, in CRYPTO’97, ed. by B.S. Kaliski Jr. Santa Barbara, CA, USA, August 17–21, 1997. LNCS, vol. 1294 (Springer, Berlin, 1997), pp. 455–469
R. Canetti, Universally composable security: A new paradigm for cryptographic protocols, in 42nd FOCS. Las Vegas, Nevada, USA, October 14–17, 2001 (IEEE Computer Society, Los Alamitos, 2001), pp. 136–145
R. Canetti, D. Micciancio, O. Reingold, Perfectly one-way probabilistic hash functions (preliminary version), in 30th ACM STOC. Dallas, Texas, USA, May 23–26, 1998 (ACM Press, New York, 1998), pp. 131–140
W. Diffie, M.E. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory 22(6), 644–654 (1976)
Y. Dodis, A. Smith, Correcting errors without leaking partial information, in 37th ACM STOC, ed. by H.N. Gabow, R. Fagin. Baltimore, Maryland, USA, May 22–24, 2005 (ACM Press, New York, 2005), pp. 654–663
O. Goldreich, R. Ostrovsky, Software protection and simulation of oblivious rams. J. ACM 43(3), 431–473 (1996)
O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM 33, 792–807 (1986)
O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991)
S. Goldwasser, Y. Tauman Kalai, On the impossibility of obfuscation with auxiliary input, in 46th FOCS. Pittsburgh, PA, USA, October 23–25, 2005 (IEEE Computer Society, Los Alamitos, 2005), pp. 553–562
S. Goldwasser, S. Micali, Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)
S. Goldwasser, G.N. Rothblum, On best-possible obfuscation, in TCC 2007, ed. by S.P. Vadhan. Amsterdam, The Netherlands, February 21–24, 2007. LNCS, vol. 4392 (Springer, Berlin, 2007), pp. 194–213
S. Hada, Zero-knowledge and code obfuscation, in ASIACRYPT 2000, ed. by T. Okamoto. Kyoto, Japan, December 3–7, 2000. LNCS, vol. 1976 (Springer, Berlin, 2000), pp. 443–457
D. Hofheinz, D. Unruh, Simulatable security and polynomially bounded concurrent composability, in 2006 IEEE Symposium on Security and Privacy. Berkeley, California, USA, May 21–24, 2006 (IEEE Computer Society, Los Alamitos, 2006), pp. 169–183
D. Hofheinz, J. Malone-Lee, M. Stam, Obfuscation for cryptographic purposes, in TCC 2007, ed. by S.P. Vadhan. Amsterdam, The Netherlands, February 21–24, 2007. LNCS, vol. 4392 (Springer, Berlin, 2007), pp. 214–232
S. Hohenberger, G.N. Rothblum, Abhi Shelat, V. Vaikuntanathan, Securely obfuscating re-encryption, in TCC 2007, ed. by S.P. Vadhan. Amsterdam, The Netherlands, February 21–24, 2007. LNCS, vol. 4392 (Springer, Berlin, 2007), pp. 233–252
R. Jaeschke, Encrypting C source for distribution. J. C Lang. Trans. 2(1) 1990
J. Katz, M. Yung, Complete characterization of security notions for probabilistic private-key encryption, in 32nd ACM STOC. Portland, Oregon, USA, May 21–23, 2000 (ACM Press, New York, 2000), pp. 245–254
C. Linn, S.K. Debray, Obfuscation of executable code to improve resistance to static disassembly, in ACM CCS 03, ed. by S. Jajodia, V. Atluri, T. Jaeger. Washington D.C., USA, October 27–30, 2003 (ACM Press, New York, 2003), pp. 290–299
B. Lynn, M. Prabhakaran, A. Sahai, Positive results and techniques for obfuscation, in EUROCRYPT 2004, ed. by C. Cachin, J. Camenisch. Interlaken, Switzerland, May 2–6, 2004. LNCS, vol. 3027 (Springer, Berlin, 2004), pp. 20–39
U.M. Maurer, R. Renner, C. Holenstein, Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, in TCC 2004, ed. by M. Naor. Cambridge, MA, USA, February 19–21, 2004. LNCS, vol. 2951 (Springer, Berlin, 2004), pp. 21–39
S. Micali, P. Rogaway, Secure computation (abstract), in CRYPTO’91, ed. by J. Feigenbaum. Santa Barbara, CA, USA, August 11–15, 1992. LNCS, vol. 576 (Springer, Berlin, 1992), pp. 392–404
M. Naor, M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, in 22nd ACM STOC. Baltimore, Maryland, USA, May 14–16, 1990 (ACM Press, New York, 1990)
A. Narayanan, V. Shmatikov, Stronger security of authenticated key exchange. Cryptology ePrint Archive, Report 2006/182 (2006). http://eprint.iacr.org/
R. Ostrovsky, W.E. Skeith III, Private searching on streaming data, in CRYPTO 2005, ed. by V. Shoup. Santa Barbara, CA, USA, August 14–18, 2005. LNCS, vol. 3621 (Springer, Berlin, 2005), pp. 223–240
C. Rackoff, D.R. Simon, Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack, in CRYPTO’91, ed. by J. Feigenbaum. Santa Barbara, CA, USA, August 11–15, 1992. LNCS, vol. 576 (Springer, Berlin, 1992), pp. 433–444
J. Rompel, One-way functions are necessary and sufficient for secure signatures, in 22nd ACM STOC. Baltimore, Maryland, USA, May 14–16, 1990 (ACM Press, New York, 1990), pp. 387–394
H. Wee, On obfuscating point functions, in 37th ACM STOC, ed. by H.N. Gabow, R. Fagin. Baltimore, Maryland, USA, May 22–24, 2005 (ACM Press, New York, 2005), pp. 523–532
Author information
Authors and Affiliations
Corresponding author
Additional information
This is the full version of [21], which appeared at the Theory of Cryptography Conference (TCC) 2007. Work by the second and third author was partially conducted while employed at the University of Bristol.
This work was partially funded by the European Commission through the ICT programme under Contract ICT-2007-216646 ECRYPT II.
Rights and permissions
About this article
Cite this article
Hofheinz, D., Malone-Lee, J. & Stam, M. Obfuscation for Cryptographic Purposes. J Cryptol 23, 121–168 (2010). https://doi.org/10.1007/s00145-009-9046-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-009-9046-1