Indistinguishability Obfuscation via Mathematical Proofs of Equivalence

on YouTube ↗52m

" summary

Claims an indistinguishability obfuscator whose security loss is independent of input length when the two programs have short formal proofs of equivalence (polynomial-size extended Frege or PV proofs), so iO extends to Turing machines with unbounded inputs. Key tools are a gate-by-gate obfuscation template that preserves circuit topology, hybridizing along a polynomial-length proof, hashing dependent-wire ciphertexts, and an iO-friendly somewhere-statistically-sound SNARG to check consistency. Construction yields polynomial security loss, supports succinct NIZKs and witness encryption, and is concretely realizable from standard assumptions.

AI-written summary · about

" chapters (25)

1. 0:00Intro
2. 0:27Indistinguishability Obfuscation (iO)
3. 0:54Indistinguishability Security (as a Game)
4. 7:49Non-Falsifiability
5. 9:29Observation: We Prove Equivalence in Math
6. 13:04What Theorems Can PV Prove?
7. 15:01What Information does a Proof Provide?
8. 21:40Define Local Equivalence
9. 23:46Alternative View: A Series of Local Changes
10. 26:39Stage II: Grow the Proof
11. 27:54Stage II: Local Equivalence
12. 30:27Stage IV: Shrink the Proof
13. 31:06Stage V: Shrink Co
14. 34:04Gate-by-Gate Obfuscation
15. 37:50Challenge: Mix-and-Match Attack
16. 39:29Replace Input with Dependent Wires
17. 39:52Define Dependence
18. 41:05Hash CT, CT
19. 41:46Apply SNARGS
20. 42:59We Use: iO-Friendly SNARGS
21. 44:46Propositional Translation [Cook'75]
22. 45:57iO for Turing Machines: Initial Attempt
23. 47:08Leverage Uniform Description
24. 48:21Efficient Construction
25. 49:27Summary & Future Directions

" related talks

• 01h 07mIndistinguishability Obfuscation via Mathematical ProofsZhengzhong Jin · Obfuscation
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)
• 46mSuccinct Obfuscation via Propositional Proofs (or: How to use pv-IO)Surya Mathialagan · Obfuscation
• 49mLower Bounds on the Overhead of Indistinguishability ObfuscationNoam Mazor · Obfuscation
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 50mApplications of Obfuscation IICraig Gentry · Cryptography Boot Camp 2015