Sub-exponential LWE ⇒ PPAD hardness

Standard model · via Fiat–Shamir · JKKZ21

Statement

If LWE is sub-exponentially hard, then PPAD contains problems that are hard on average — JKKZ21. The proof instantiates the Fiat–Shamir transform for the sum-check protocol with a lossy correlation-intractable hash family and plugs it into the reduction of CHKPRR19 from Fiat–Shamir soundness to PPAD hardness — JKKZ21.

Notes

• PPAD hardness also follows from sub-exponentially secure indistinguishability obfuscation and one-way functions: OWF + iO ⇒ PPAD hardness — BPR15. Finding a Nash equilibrium, even in two-player games, is PPAD-complete, so it is hard on average under sub-exponential LWE — DGP09, CDT09.