Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization
summary
Shows that Indistinguishability Obfuscation (IO) and MCSP mutually empower each other by concrete implications: a perfect IO secure against non‑uniform poly‑size circuits yields fixed‑polynomial circuit lower bounds for NP (and MA for imperfect IO) and super‑polynomial lower bounds for NEXP; a perfect IO secure against uniform algorithms implies ZPEXP != BPP; if MCSP ∈ BPP then statistical and computational IO coincide. Main technical tool is an optimal universal distinguisher computable in randomized polytime with an MCSP oracle that distinguishes circuit‑samplable distributions up to their statistical distance.
AI-written summary · about
chapters (4)
- 0:00Start
- 1:16Lower Bounds - The Holy Grail of Complexity Theory
- 9:17Minimum Circuit Size Problem (MCSP)
- 11:29The Complexity of MCSP
related talks
31mObfuscation of Probabilistic Circuits and Applications
49mLower Bounds on the Overhead of Indistinguishability Obfuscation
52mIndistinguishability Obfuscation via Mathematical Proofs of Equivalence
01h 12mApplications of Obfuscation I
01h 07mIndistinguishability Obfuscation via Mathematical Proofs
01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...
31mIndistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
50mApplications of Obfuscation II