Sub-exponential OWF + iO ⇒ PPAD hardness

Free reduction · standard model · BPR15 · security loss: super-polynomial, which is why both hypotheses are assumed sub-exponentially hard

Statement

If sub-exponentially secure iO and sub-exponentially secure one-way functions exist, then PPAD is hard on average: there is an efficiently sampleable distribution over PPAD instances such that for all efficient $\mathcal{A}$, the probability that $\mathcal{A}$ outputs a solution is negligible — BPR15.