Obfuscation for Cryptographic Purposes

Dennis Hofheinz; John Malone-Lee; Martijn Stam

Paper 2006/463

Obfuscation for Cryptographic Purposes

Dennis Hofheinz, John Malone-Lee, and Martijn Stam

Abstract

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. Several definitions for obfuscation exist. However, most of them are either too weak for or incompatible with cryptographic applications, or have been shown impossible to achieve, or both. We give a new definition of obfuscation and argue for its reasonability and usefulness. In particular, we show that it is strong enough for cryptographic applications, yet we show that it has the potential for interesting positive results. We illustrate this with the following two results: - If the encryption algorithm of a secure secret-key encryption scheme can be obfuscated according to our definition, then the result is a secure public-key encryption scheme. - A uniformly random point function can be easily obfuscated according to our definition, by simply applying a one-way permutation. Previous obfuscators for point functions, under varying notions of security, are either probabilistic or in the random oracle model (but work for arbitrary distributions on the point function). On the negative side, we show that - Following Hada and Wee, any family of deterministic functions that can be obfuscated according to our definition must already be ``approximately learnable.'' Thus, many deterministic functions cannot be obfuscated. However, a probabilistic functionality such as a probabilistic secret-key encryption scheme can potentially be obfuscated. In particular, this is possible for a public-key encryption scheme when viewed as a secret-key scheme. - There exists a secure probabilistic secret-key encryption scheme that cannot be obfuscated according to our definition. Thus, we cannot hope for a general-purpose cryptographic obfuscator for encryption schemes.

Note: Comparison of our obfuscation definition to the one from [Goldwasser and Tauman Kalai 2005] added

Metadata

Available format(s): PDF PS
Category: Foundations
Publication info: Published elsewhere. Accepted for TCC 2007
Keywords: obfuscation point functions
Contact author(s): Dennis Hofheinz @ cwi nl
History: 2007-03-08: last of 3 revisions; 2006-12-08: received; See all versions
Short URL: https://ia.cr/2006/463
License: CC BY

BibTeX

@misc{cryptoeprint:2006/463,
      author = {Dennis Hofheinz and John Malone-Lee and Martijn Stam},
      title = {Obfuscation for Cryptographic Purposes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/463},
      year = {2006},
      url = {https://eprint.iacr.org/2006/463}
}