Cryptology ePrint Archive: Report 2013/701

More on the Impossibility of Virtual-Black-Box Obfuscation with Auxiliary Input

Nir Bitansky and Ran Canetti and Omer Paneth and Alon Rosen

Abstract: We show that if there exist indistinguishability obfuscators for a certain class C of circuits then there do not exist independent-auxiliary-input virtual-black-box (VBB) obfuscators for any family of circuits that compute a pseudo-entropic function. A function f_k is pseudo-entropic if it is hard, given oracle access to f_k but without asking explicitly on a value x, to distinguish f_k(x) from a random variable with some real entropy.

This strengthens the bound of Goldwasser and Kalai [FOCS `05, ePrint `13] that rules out dependent-auxiliary-input VBB obfuscation for the same set of circuit families, assuming inditinguishability obfuscators for another class, C', of circuits. That is, while they only rule out the case where the adversary and the simulator obtain auxiliary information that depends on the actual (secret) obfuscated function, we rule out even the case where the auxiliary input depends only on the (public) family of programs.

Category / Keywords:

Date: received 27 Oct 2013, last revised 18 Feb 2014

Contact author: omerpa at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140218:134641 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]