On the Assumptions Used for Obfuscation

on YouTube ↗01h 06m

" summary

Survey compares four concrete assumptions used to build obfuscation: LWE, SXDH, local PRGs, and LPN. Gives concrete regimes for LPN (constant noise + linear samples → exponential best attacks; inverse‑poly noise → subexponential attacks via low‑weight kernel vectors and BKW variants), proves decision→search via Goldreich‑Levin, and describes Zq/LPN lifting that lets one “plant” a short kernel vector for CCA‑style keys. Shows local PRGs from sparse LPN require expansion and resilient, high‑degree predicates, and orders primitives by available homomorphism: none → bounded addition → bilinear → full.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 0:48Obfuscation
3. 4:24Learning Parity with Noise [BFKL94]
4. 6:15Decoding Random Linear Code GKLE
5. 13:52Known Attacks
6. 19:09Simple Distinguishing Attack
7. 24:33Pseudorandomness
8. 30:51Random Self-Reducibility
9. 31:22Dual Version: Syndrome Decoding
10. 32:44Corollary: Planting Short Vector in Kerne
11. 34:02LPN: Evidence for Hardness
12. 38:17LPN: Features
13. 40:47Variants
14. 52:59Learning with Errors Variant Regevos
15. 54:05Locally Computable Functions (NC) Each output depends on constant number of inputs
16. 54:46Lin-PRGs in NC
17. 56:53Poly-Stretch PRG in NC
18. 59:09Generalization to Long Output

" related talks

• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 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
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 01h 29mLattices, Multilinear Maps and Program ObfuscationYilei Chen · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 05mObfuscation from Noisy Linear FEShweta Agrawal · Lattices: New Cryptographic Capabilities 2020