On the Cryptographic Hardness of Finding a Nash Equilibrium

on YouTube ↗23m

" summary

Shows that, assuming indistinguishability obfuscation with subexponential security plus one-way functions, End-of-the-Line (hence PPAD and Nash equilibrium) is sub-exponentially hard on average. Construction embeds a long path using a pseudo-random function with obfuscated successor/predecessor, proves indistinguishability via sparse-trigger techniques and puncturing, and resolves the predecessor issue by simulating it through reversible simulation (Bennett) and a verifiability trick. Concrete hardness parameters and an explicit hard distribution are given.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:16The Story Line
3. 0:40Game Theory and Nash Equilibrium
4. 1:43The CS Perspective
5. 3:55The Class PPAD [Papadimitriou 94]
6. 4:49End of the Line Problem (EOL)
7. 6:11PPAD and NASH [Papadimitriou 94]
8. 8:53Program Obfuscation
9. 11:47Main Theorem
10. 12:34Hard EOL Instances
11. 17:57A Useful Lemma
12. 19:07Step 2 - Proof
13. 21:09The Problem of Going Backwards

" related talks

• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 50mApplications of Obfuscation IICraig Gentry · Cryptography Boot Camp 2015
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 46mOn Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast DerandomizationEmanuele Viola, Ronen Shaltiel · ITCS 2022
• 31mIndistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango · Proof Complexity and Meta-Mathematics 2023