iO + NP ⊄ io-BPP ⇒ OWF

Standard model · KMNPRY14

Statement

If NP ⊄ io-BPP and an efficient indistinguishability obfuscator for all polynomial-size circuits exists, even one that is only approximately correct, then one-way functions exist — KMNPRY14. The complexity hypothesis cannot be dropped: if $\mathbf{P}=\mathbf{NP}$, iO exists, by outputting the lexicographically first circuit of the same size computing the same function — KMNPRY14 — while one-way functions do not (OWF inversion ∈ NP) — folklore.

Notes

• With no complexity assumption, iO yields statistical zero-knowledge arguments for $\mathbf{NP}$ (iO ⇒ Statistical ZK arguments for NP) — KMNPRY14.
• An alternative version replaces $\mathbf{NP}⊈\mathbf{io}\text{-}\mathbf{BPP}$ by the assumption that some $\mathbf{NP}$ problem is hard on average — KMNPRY14.