Tales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential Privacy

on YouTube ↗48m

" summary

Three concrete results use obfuscation and related primitives to resolve open problems: assuming indistinguishability obfuscation and NP ≠ coNP, there is no efficient deterministic algorithm for Avoid (circuit range avoidance), which yields the first separation of PV1 from APC1; computing conditional time‑bounded Kolmogorov complexity becomes NP‑hard under iO via black‑box reductions and achieves unconditional near‑optimal hardness in the sublinear regime using the generic multilinear map model; and a client–server task is achievable under computational differential privacy but impossible statistically, built using differing‑inputs obfuscation plus keyless collision‑resistant hash functions, and the constructions work.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 2:57Talk Goal
3. 13:53Bounded Arithmetic
4. 15:50Three Questions
5. 19:20An Idea
6. 25:09Two Questions
7. 38:10n.99 -Distance Problem
8. 44:59Zero Hash d-Distance Problem

" related talks

• 31mIndistinguishability Obfuscation, Range Avoidance, and Bounded ArithmeticRahul Ilango · Proof Complexity and Meta-Mathematics 2023
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 31mObfuscation of Probabilistic Circuits and ApplicationsHuijia Lin · Securing Computation (Simons Institute, June 2015)
• 49mLower Bounds on the Overhead of Indistinguishability ObfuscationNoam Mazor · Obfuscation
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 50mApplications of Obfuscation IICraig Gentry · Cryptography Boot Camp 2015