Sub-exponential DDH ⇒ PPAD hardness

Standard model · via Fiat–Shamir · KLV23

Statement

If DDH is sub-exponentially hard for some group generator (no pairing is needed), then PPAD contains problems that are sub-exponentially hard on average — KLV23. The proof instantiates the Fiat–Shamir transform under DDH for a variant of the sum-check protocol, using a correlation-intractable hash family, and PPAD hardness follows from the soundness of that transform by the route of CHKPRR19 — KLV23.

Notes

• The same technique, applied to a variant of the GKR protocol, gives unambiguous SNARGs for bounded-depth computations under sub-exponential DDH — KLV23.
• PPAD hardness also follows, by the same Fiat–Shamir route, from sub-exponential LWE: Sub-exponential LWE ⇒ PPAD hardness — JKKZ21.