Indistinguishability Obfuscation from Well-Founded Assumptions

on YouTube ↗57m

" summary

Constructs iO by reducing it to a structured seed PRG built from two assumptions: sparse LPN and an NC0 Boolean PRG with stretch n^{1+τ} (τ arbitrarily small, e.g. 0.001). Public seed is LPN samples as public seed that hide the input; a short private seed stores precomputed low-degree monomials and compressed correction data via low-rank matrix bucketing to fix about M·λ/L^δ errors. Evaluation uses bilinear (degree‑2) operations; security loses a 1/λ factor but admits amplification.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:53Learning Parity with Noise
3. 3:58Boolean PRGs
4. 6:50Structured PRGs
5. 10:23Implausibility Results
6. 13:30Constructing the Model
7. 27:49Finding a Short Seed
8. 28:29Preprocessing
9. 31:29Bad output bits
10. 35:24One naive approach
11. 54:18Questions

" related talks

• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 42mObfuscation IV: A New Assumption enabling iOAmit Sahai · Lattices: New Cryptographic Capabilities 2020
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 52mIndistinguishability Obfuscation via Mathematical Proofs of EquivalenceZhengzhong Jin · Proof Complexity and Meta-Mathematics 2023