Statistical 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 statistically secure indistinguishability obfuscator is secure for sampled circuit pairs, even against unbounded distinguishers. Let a polynomial bound the size of the circuits a sampler outputs. At each there are finitely many equivalent pairs of equal size at most , so one of them maximizes the statistical distance between its two obfuscations; these maximizers form a pair of circuit families, so the maximum is negligible. Every distinguisher then has advantage at most plus the probability that the sampled pair is not equivalent — standard.