Sub-exponentially secure iO ⇒ iO for sampled circuit pairs

Fully-black-box reduction · standard model · folklore · security loss: additive: the probability that the sampled pair is not functionally equivalent

Statement

A sub-exponentially secure indistinguishability obfuscator is secure for sampled circuit pairs. Its adversaries are circuits of size , hence non-uniform. For a non-uniform PPT sampler and distinguisher , averaging over the coins of gives at each an equivalent pair and its auxiliary output on which the advantage of is at least its overall advantage minus the probability of a non-equivalent pair. These pairs form a pair of circuit families of polynomial size, and with hard-wired is a circuit of polynomial size, below for large , so its advantage on them is at most — standard.