Expedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...

on YouTube ↗01h 08m

" summary

Claims a provable route to indistinguishability obfuscation built from three well-studied assumptions (LPN over large fields, simple local PRGs computable in NC0, and decision linear over symmetric bilinear maps) requiring subexponential hardness, and reduces full iO to polynomial-size XIO on NC0. Key tools are an LPN-based homomorphic scheme with approximate linear decryption, compression of sparse error vectors via low-rank encodings, and degree-two decoding via pairings; the construction is theoretical and works under the stated assumptions but remains far from practical.

AI-written summary · about

" chapters (35)

1. 0:00Introduction to obfuscation
2. 2:32Ideal obfuscation concepts
3. 5:37Impossibility and IO security
4. 11:30Heuristics and VBB models
5. 12:49Advanced VBB justifications
6. 15:01Punctured program techniques
7. 16:06IO as a master tool
8. 16:56Foundational IO constructions
9. 18:00Multilinear map candidates
10. 21:50Scientific thriller of IO
11. 23:17Minimal primitives for IO
12. 24:51Foundations from LPN
13. 25:54Exponential efficiency IO
14. 27:15The JS construction process
15. 30:31Randomized encoding of circuits
16. 32:43Degree reduction techniques
17. 35:03LPN-based homomorphic encryption
18. 36:04Hardness of decoding LPN
19. 38:07Encryption and approximate decryption
20. 39:14Homomorphic sparse evaluation
21. 41:47Degree-two decoding challenges
22. 42:45Relaxation and decoding secrets
23. 43:54Succinct decoding with compression
24. 44:51Sparse error vector compression
25. 47:19Summary of LPN homomorphism
26. 47:30Final construction pipeline
27. 48:39Future directions and open goals
28. 50:19Status of lattice candidates
29. 51:02Community optimism poll
30. 51:45Standard lattice assumptions
31. 52:04Security based on LWE hints
32. 52:42Circular security and FHE
33. 53:15Designing secure hints
34. 55:20Random opening assumptions
35. 59:12Conclusion and Q&A

" related talks

• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023