Obfuscation via GGH15 Encodings, 10 Years Later

on YouTube ↗51m

" summary

Describes a concrete candidate obfuscator built from GGH15 encodings that aims to get iO, null‑iO and witness encryption, with security arguments for permutation and corner‑one branching programs from LWE and a small‑scale implementation by Halevi et al. Exposes a practical rank leak attack that picks L^2 inputs (combinatorial rectangle), evaluates encodings and reads matrix rank to recover intermediate state, and gives fixes: avoid encoding zeros (null‑iO), pad to read‑λ, or require evasive LWE (add noise and local aux inputs) to restore proofs.

AI-written summary · about

" chapters (11)

1. 0:00GGH15 introduction
2. 2:06GGH15 encodings for obfuscation
3. 6:44Kilian-style randomization
4. 9:58Null-iO security
5. 12:54Permutation programs proof
6. 15:44Rank analysis attack
7. 27:54Read-many branching programs
8. 29:43Evasive LWE for null-iO
9. 35:54Null-iO from evasive LWE
10. 39:17Open problems
11. 40:45Q&A

" related talks

• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 01h 15mThe Journey Towards Program ObfuscationYael Tauman Kalai · Simons Institute Workshop: New Developments in Obfuscation
• 58mObfuscation IAmit Sahai · Cryptography Boot Camp 2015
• 01h 02mObfuscation IIAmit Sahai · Cryptography Boot Camp 2015
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 01h 04mCryptanalysis of Candidate Program ObfuscatorsYilei Chen · Lattices: New Cryptographic Capabilities 2020