Contention in Cryptography: Obfuscation, Leakage, UCE and the AI-DHI Assumptions
summary
Shows that auxiliary-input DDH (AI-DDH) cannot hold simultaneously with a modest form of virtual grey-box (VGB) obfuscation: construct an auxiliary-input generator that outputs (k,A) where A contains a VGB obfuscation of a point-check circuit, use that obfuscation plus a group element pair (r,r^k) to distinguish real from random exponents, and argue unpredictability of k via the VGB simulator and discrete-log information bounds. Also proves tight connections between AIPO and UCE and gives IO-based impossibilities for certain UCE classes.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:58Possible approach: relations among assumptions
- 3:20Obfuscation (BGI+01)
- 4:22Point functions
- 7:15Auxiliary-information generator
- 7:47Auxiliary-input point obfuscation
- 9:44Canetti's construction [C97]
- 14:14Proof - Auxiliary-information
- 15:21Proof - Unpredictability
- 17:49VGB-security implies existence of (unbounded)
- 22:57Universal computational extractors BHK13 Standard-model assumption for random- oracle instantiation
- 27:53Conclusions
related talks
44mThe Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
21mDecision and Complexity of Dolev-Yao Hyperproperties
36mPublic Key Cryptography
37mFrontiers in Cryptography
23mUniversal Composability is Robust Compilation
21mWhen Obfuscations Preserve Cryptographic Constant-Time
30mKEYNOTE Building Succinct Arguments from Ideal Hash Functions
01h 06mOn the Assumptions Used for Obfuscation