How to Encrypt a Functionality

on YouTube ↗01h 04m

" summary

Claims a concrete candidate for indistinguishability obfuscation built from a new “algebraic jigsaw puzzle” instantiation of approximate multilinear maps: polynomials mod X^N+1 and a large prime q, a small secret G, noisy encodings and a restricted zero‑testing element. It shows how to evaluate NC1 via Barrington’s matrix trick, bootstraps to general circuits with FHE, proves security against natural algebraic attacks, reports huge polynomial overhead so it is impractical now, and notes no known quantum attacks.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:55Explanation
3. 3:44Examples
4. 11:18Encryption Analogy
5. 13:00Encrypting Functionality
6. 17:18Definitions
7. 20:36Indistinguishable Obfuscation
8. 26:58Functionality Encryption
9. 39:24Puzzle Pieces
10. 43:39Puzzle Piece
11. 49:00Encrypting Functions
12. 55:18Conclusion
13. 57:48In principle

" related talks

• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 01h 02mObfuscation IIAmit Sahai · Cryptography Boot Camp 2015
• 58mObfuscation IAmit Sahai · Cryptography Boot Camp 2015
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 01h 15mThe Journey Towards Program ObfuscationYael Tauman Kalai · Simons Institute Workshop: New Developments in Obfuscation
• 01h 04mCryptanalysis of Candidate Program ObfuscatorsYilei Chen · Lattices: New Cryptographic Capabilities 2020