No reduction from iO to statistical iO

Conditional · against free reductions · assuming Indistinguishability Obfuscation · GR07

Statement

If an efficient statistically secure indistinguishability obfuscator exists for 3-CNF formulas, then some $\mathbf{NP}$-complete problem lies in SZK, $\mathbf{coNP}\subseteq \mathbf{AM}$, and the polynomial hierarchy collapses to its second level — GR07, BHZ87. GR07 state the collapse for statistically secure best-possible obfuscators of 3-CNF formulas, even inefficient ones, and show that efficient indistinguishability obfuscators are best-possible obfuscators — GR07. Hence, if iO exists, no reduction of any kind turns it into statistical iO unless $\mathbf{coNP}\subseteq \mathbf{AM}$.

Sketch

For a 3-CNF $\phi$ and the constant-$0$ formula $Z$ of the same size, $i\mathcal{O}(1^{\lambda },\phi )$ and $i\mathcal{O}(1^{\lambda },Z)$ are statistically close if $\phi$ is unsatisfiable, and have disjoint supports by perfect correctness if it is satisfiable. Both are sampled by polynomial-size circuits, so this reduces $\mathrm{SAT}$ to Statistical Difference, giving $\mathbf{NP}\subseteq \mathbf{SZK}\subseteq \mathbf{coAM}$ — SV03, For87.

Notes

• The collapse extends to statistically secure obfuscators that are only approximately correct — Vol21.