Indistinguishability Obfuscation from Bilinear Maps and LPN Variants

on YouTube ↗46m

" summary

Constructs indistinguishability obfuscation from three assumptions: bilinear maps, large-field LPN, and a new local functions with noise (LFN) assumption that replaces PRGs-in-NC0. The paper builds degree-2 functional encryption from bilinear maps, uses algebraic compression (sparse error → low-rank u·v) and large-field LPN to get constant-degree FE, then uses randomized encodings and a structured-seed NC0 PRG from LFN to lift to full FE and IO with subexponential security. Practical issues around sampling sparse matrices are handled via a combiner.

AI-written summary · about

" chapters (10)

1. 0:00Indistinguishability obfuscation intro
2. 2:20History and assumptions for IO
3. 6:43Local functions with noise
4. 10:16Functional encryption in IO
5. 13:06Large field LPN and FE
6. 21:12Randomized encodings and garbled circuits
7. 26:10Polynomial stretch PRGs
8. 32:01Structured seed PRGs
9. 35:19Sparse LPN security
10. 39:59Open questions in IO

" related talks

• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mOn the Assumptions Used for ObfuscationBenny Applebaum · Simons Institute Workshop: New Developments in Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 05mObfuscation from Noisy Linear FEShweta Agrawal · Lattices: New Cryptographic Capabilities 2020
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 53mLPN Based IO Part 2Rachel Lin · Simons Institute Workshop: New Developments in Obfuscation
• 57mIndistinguishability Obfuscation from Well-Founded AssumptionsAayush Jain · Simons Institute Workshop: New Developments in Obfuscation