Tutorial on obfuscation
summary
Survey claims a concrete blueprint to get iO from LPN + local PRGs + bilinear maps: randomized encodings (garbled circuits) reduce evaluation to a single degree-two concealment step handled by bilinear maps, local PRGs are compressed via an LPN-based trick, and recursive truth-table compression yields polynomial-size iO. It also gives an oracle result: pseudorandom Oracle lets one realize ideal/VBB obfuscation assuming functional encryption. Main caveats: all constructions need sub-exponential hardness and the bilinear-map piece breaks under quantum attacks; LWE-based alternatives currently face noise-leakage attacks.
AI-written summary · about
chapters (8)
- 0:00Program obfuscation survey
- 1:48Virtual black box definition
- 11:22Tutorial overview
- 13:11Indistinguishability obfuscation assumptions
- 30:21Beyond indistinguishability obfuscation
- 41:34Pseudorandom Oracle model
- 53:39Post-quantum obfuscation challenges
- 1:01:06Open problems and future
related talks
01h 26mObfuscation 1
46mIndistinguishability Obfuscation from Bilinear Maps and LPN Variants
01h 15mThe Journey Towards Program Obfuscation
01h 06mOn the Assumptions Used for Obfuscation
01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...
58mObfuscation 2
38mRecent Advances on Foundations of Program Obfuscation
57mIndistinguishability Obfuscation from Well-Founded Assumptions