iO + OWP ⇒ CLS hardness

Free reduction · standard model · HY17

Statement

If indistinguishability obfuscation for all polynomial-size circuits and one-way permutations exist, then CLS is hard on average: there is an efficiently samplable distribution over instances of End-of-Metered-Line, a problem in CLS, such that for all efficient $\mathcal{A}$, the probability that $\mathcal{A}$ outputs a solution is negligible — HY17. HY17 reduce Sink-of-Verifiable-Line to End-of-Metered-Line and apply the reduction to the hard Sink-of-Verifiable-Line instances built from iO — HY17, BPR15, GPS16.

Notes

• In the black-box setting, with $S$, $P$ and $V$ given as oracles, every randomized algorithm needs $\Omega (2^{n/2}/\sqrt{n})$ queries to solve End-of-Metered-Line — HY17.
• Since CLS is contained in PPAD (CLS hardness ⇒ PPAD hardness) — DP11 — the result strengthens iO + OWP ⇒ PPAD hardness — GPS16.