Jump to content
Tuts 4 You

The Impossibility of Obfuscation with a Universal Simulator


About This File

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 F = {fs} be a circuit family with super-polynomial pseudo-entropy, and suppose O is a candidate obfuscator with universal simulator S. We demonstrate the existence of an adversary A that, given the obfuscation O(fs), learns a predicate the simulator S cannot learn from the code of A and black-box access to fs. Furthermore, this is true in a strong sense: for any secret predicate P that is not learnable from black-box access to fs, there exists an adversary that given O(fs) efficiently recovers P (s), whereas given oracle access to fs 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.


User Feedback

Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...