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

Rahul Ilango (MIT) https://simons.berkeley.edu/talks/rahul-ilango-mit-2023-05-03 Minimal Complexity Assumptions for Cryptography In this talk, I will discuss three recent results that use obfuscation to answer open questions in various areas of theoretical computer science, including bounded arithmetic, derandomization, metacomplexity, average-case complexity, and differential privacy. This talk will focus on giving a brief overview of these results and connections, emphasizing intuition and ideas. Below is a short description of each result. The first work is about Circuit Range Avoidance (Avoid), a problem where the goal is to output a string outside the range of a given length-expanding circuit. While there is a simple randomized algorithm for Avoid (output a random string), the existence of an efficient deterministic algorithm for Avoid was a tantalizing open question with many applications, including explicit constructions of highly rigid matrices. We show there is *no* efficient deterministic algorithm for Avoid assuming indistinguishability obfuscation (iO) and that NP does not equal coNP. Building on this, we answer an open question in bounded arithmetic. Specifically, we give the first separation of Cook's theory PV1 from Jeřábek's theory APC1 under plausible assumptions. The second work studies a problem in metacomplexity: the task of computing conditional time-bounded Kolmogorov complexity. Recently, Hirahara showed that proving this problem is NP-hard in the "superlinear regime" would eliminate Heuristica (where SAT average-case easy but worst-case hard). This naturally leads to the question: should we expect this problem to be NP-hard? We show that if iO exists, then this problem is indeed NP-hard under *black-box* polynomial-time reductions. Furthermore, we use constructions in the generic multilinear map model to show *unconditionally* near-optimal NP-hardness of approximation in the "sublinear" regime. The last work focuses on differential privacy. Differential privacy is usually studied with an all-powerful adversary. A longstanding open question is whether, by relaxing the adversary to be computational instead of statistical, one can accomplish tasks (in the usual client-server setting) that were previously impossible. We give the first construction of such a task under any plausible assumption. Specifically, our assumptions involve the existence of differing inputs obfuscation and keyless collision-resistant hash functions. Previously, even a candidate for such a task was unknown. This talk is based on joint works with Badih Ghazi, Yizhi Huang, Pritish Kamath, Ravi Kumar, Jiatu Li, Pasin Manurangsi, Hanlin Ren, and Ryan Williams.