You are looking at a specific version 20131024:080103 of this paper. See the latest version.

Paper 2013/665

A Note on the Impossibility of Obfuscation with Auxiliary Input

Shafi Goldwasser and Yael Tauman Kalai

Abstract

In this note we revisit the problem of obfuscation with auxiliary inputs. We show that the existence of indistinguishablity obfuscation (iO) implies that all functions with sufficient "pseudo-entropy" cannot be obfuscated with respect to a virtual box definition (VBB) in the presence of (dependent) auxiliary input. Namely, we show that for any candidate obfuscation O and for any function family F={f_s} with sufficient pseudo-entropy, there exists an (efficiently computable) auxiliary input aux, that demonstrates the insecurity of O. This is true in a strong sense: given O(f_s) and aux one can efficiently recover the seed s, whereas given aux and oracle access to f_s it is computationally hard to recover s. A similar observation was pointed out in a recent work of Goldwasser et. al. (Crypto 2013), assuming *extractable* witness encryption. In this note we show that the extractability property of the witness encryption is not needed to get our negative result, and all that is needed is the existence of witness encryption, which in turn can be constructed from iO obfuscation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
obfuscationauxiliary inputs
Contact author(s)
yaelism @ gmail com
History
2014-02-18: last of 2 revisions
2013-10-24: received
See all versions
Short URL
https://ia.cr/2013/665
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.