No fully-black-box reduction from PPAD hardness to OWF

Unconditional · against fully-black-box reductions · RSS17

Statement

There is no fully-black-box construction of a one-way function from average-case PPAD hardness, a hard-on-average distribution of End-of-Line instances, nor even from a hard-on-average distribution of instances of the sink-of-verifiable-line problem (SVL) — RSS17. An SVL instance consists of a source $x_s\in \{0,1{\}}^n$, a target index $T\in [2^n]$, a successor circuit $S:\{0,1{\}}^n\to \{0,1{\}}^n$ and a verification circuit $V:\{0,1{\}}^n\times [T]\to \{0,1\}$, promised to accept $(x,i)$ iff $x=S^{i-1}(x_s)$; its unique solution is the $x$ with $V(x,T)=1$ — BPR15. A hard-on-average SVL distribution gives a hard-on-average End-of-Line distribution by a black-box construction — BPR15, RSS17 — so the separation from SVL hardness implies the one from PPAD hardness.

Notes

• SVL hardness has no black-box construction from injective trapdoor functions, nor from any primitive that exists relative to a random injective trapdoor function oracle, collision-resistant hash functions among them — RSS17. Nor has it one from average-case PPAD hardness, even from a hard-on-average distribution of End-of-Line instances that each have a unique solution — RSS17.
• There is no black-box construction of a hard-on-average distribution of End-of-Line instances over $\{0,1{\}}^n$ with $2^{n^{o(1)}}$ solutions from injective trapdoor functions, nor from any primitive that exists relative to a random injective trapdoor function oracle — RSS17. The obfuscation-based constructions of Sub-exponential OWF + iO ⇒ PPAD hardness and iO + OWP ⇒ PPAD hardness give instances with a unique solution — RSS17.
• With a one-way function added as a hypothesis, SVL hardness still gives no key agreement by a fully-black-box construction: No fully-black-box reduction from PPAD hardness + OWF to KE — RSS17.