The Impossibility of Obfuscation with a Universal Simulator

Henry Cohn, Shafi Goldwasser, and 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.

Note: Added a note: "This is an out of date draft. The paper was merged with More on the Impossibility of Virtual-Black-Box Obfuscation with Auxiliary Input by Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen to form The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator by all seven authors (available as arXiv:1401.0348)."

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
obfuscation
Contact author(s)
yaelism @ gmail com
History
2014-02-18: last of 2 revisions
See all versions
Short URL
https://ia.cr/2013/665

CC BY

BibTeX

@misc{cryptoeprint:2013/665,
author = {Henry Cohn and Shafi Goldwasser and Yael Tauman Kalai},
title = {The Impossibility of Obfuscation with a Universal Simulator},
howpublished = {Cryptology ePrint Archive, Paper 2013/665},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/665}},
url = {https://eprint.iacr.org/2013/665}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.