Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic

on YouTube ↗31m

" summary

Main claim: under two assumptions—NP not in coAM infinitely often and existence of subexponentially secure indistinguishability obfuscation—the theory PV1 cannot prove the dual weak pigeonhole principle for PV functions, so APC1 is strictly stronger. Proof converts a hypothetical PV1 proof via KPT witnessing into a deterministic constant‑round Circuit Range Avoidance student‑teacher algorithm, then uses iO to build circuits C_{φ,y} (output y on satisfying x, else 0) so that such an algorithm yields NP in coAM infinitely often (or NP=coNP in the one‑round case).

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 2:40Proof of PV1
3. 8:55What is PV1
4. 12:25Range Avoidance Algorithm
5. 15:23Indistinguishable
6. 16:57Indistinguishability Application
7. 20:23Proof
8. 22:00Reduction

" related talks

• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 01h 07mIndistinguishability Obfuscation via Mathematical ProofsZhengzhong Jin · Obfuscation
• 56mToward Obfuscation from Affine Determinant ProgramsMark Zhandry · Obfuscation
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)
• 01h 08mIncrementally Verifiable Computation for NP from Standard AssumptionsSurya Mathialagan · Proofs (Simons Institute)
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 49mLower Bounds on the Overhead of Indistinguishability ObfuscationNoam Mazor · Obfuscation