Welcome to the resource topic for 2013/665
Title:
The Impossibility of Obfuscation with a Universal Simulator
Authors: Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai
Abstract:We show that indistinguishability obfuscation implies that all functions with sufficient ``pseudo-entropy’’ cannot be obfuscated under a virtual black box definition with a universal simulator. Let {\cal F}=\{f_s\} be a circuit family with super-polynomial pseudo-entropy, and suppose {\cal O} is a candidate obfuscator with universal simulator \Sim. We demonstrate the existence of an adversary \Adv that, given the obfuscation {\cal O}(f_s), learns a predicate the simulator \Sim cannot learn from the code of \Adv and black-box access to f_s. Furthermore, this is true in a strong sense: for \emph{any} secret predicate P that is not learnable from black-box access to f_s, there exists an adversary that given {\cal O}(f_s) efficiently recovers P(s), whereas given oracle access to f_s and given the code of the adversary, it is computationally hard to recover P(s). We obtain this result by exploiting a connection between obfuscation with a universal simulator and obfuscation with auxiliary inputs, and by showing new impossibility results for obfuscation with auxiliary inputs.
ePrint: https://eprint.iacr.org/2013/665
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .