Differing-inputs obfuscation (diO) ⇒ 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

Take differing-inputs obfuscation against non-uniform samplers, difference-finders and distinguishers. Then a differing-inputs obfuscator is secure for sampled circuit pairs. Given a sampler , the diO sampler runs and outputs its pair with as auxiliary input when , and with otherwise. Its pairs have equal size and have a differing input only when the pair of is not equivalent, which has negligible probability, so no difference-finder succeeds except with negligible probability. The diO guarantee for this sampler, with the distinguisher , bounds the advantage of for by the diO advantage plus the probability of a non-equivalent pair — standard.