More on the Impossibility of Virtual-Black-Box Obfuscation with Auxiliary Input.
Nir Bitansky, Ran Canetti, Omer Paneth, Alon Rosen · 2013
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 fk is pseudo-entropic if it is hard, given oracle access to fk but without asking explicitly on a value x, to distinguish fk(x) from a random variable with some real entropy. This strengthens the bound of Goldwasser and Kalai [FOCS ‘05, ePrint ‘13] that rules out dependentauxiliary-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. 1