Beyond P versus NP: Using Complexity Theory in Obfuscation and Vice-Versa
summary
Claim: iO plus stronger-than-P≠NP complexity assumptions yields cryptographic objects whose hardness matches naive attacks. Techniques combine indistinguishability obfuscation, obfuscated point function constructions and punctured PRF hybrids, plus Valiant–Vazirani and Goldwasser–Sipser style worst-case→average-case reductions. Concrete outcomes include a keyed PRF-based construction that becomes an optimal one‑way function with inversion success ≤ poly(t)/2^n, and one‑way families with direct‑product hardness that scales as p^k for k instances. Constructions are explicit and work under the stated subexponential iO and NP hardness assumptions.
AI-written summary · about
chapters (12)
- 0:00Introduction and outline
- 1:44Defining obfuscation
- 4:22Missing cryptographic primitives
- 7:00Examples of missing primitives
- 14:20High-level research results
- 16:53Two-step research approach
- 22:06Historical interlude
- 25:01Hardness of NP
- 30:39Reduction and warmup
- 39:39Proof sketch
- 43:35Constructing optimal functions
- 49:42Summary and future directions
related talks
01h 12mApplications of Obfuscation I
48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy
31mObfuscation of Probabilistic Circuits and Applications
01h 04mTutorial on obfuscation
31mIndistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
50mApplications of Obfuscation II
52mIndistinguishability Obfuscation via Mathematical Proofs of Equivalence
58mObfuscation 2