iO + OWP ⇒ PPAD hardness

Free reduction · standard model · GPS16 · security loss: polynomial

Statement

If polynomially secure indistinguishability obfuscation for all polynomial-size circuits and polynomially secure one-way permutations exist, then PPAD is hard on average: there is an efficiently samplable distribution over End-of-Line instances such that for all efficient $\mathcal{A}$, the probability that $\mathcal{A}$ outputs a solution is negligible — GPS16. No complexity leveraging is needed: the earlier construction of Sub-exponential OWF + iO ⇒ PPAD hardness assumes sub-exponentially secure iO and one-way functions — BPR15.

Notes

• Polynomially secure compact public-key functional encryption can replace iO: together with one-way permutations it also makes PPAD hard on average — GPS16.