Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization

Ilya Volkovich (Boston College) https://simons.berkeley.edu/talks/ilya-volkovich-boston-college-2023-05-03 Minimal Complexity Assumptions for Cryptography We study close connections between Indistinguishability Obfuscation (IO) and the Minimum Circuit Size Problem (MCSP), and argue that algorithms for one of MCSP or IO would empower the other one. Some of our main results are: If there exists a perfect (imperfect) IO that is computationally-secure against non-uniform polynomial-size circuits, then we obtain fixed-polynomial lower bounds against NP (MA) In addition, perfect computationally-secure IO against non-uniform polynomial-size circuits implies super-polynomial lower bounds against NEXP. On the uniform side, perfect computationally-secure IO against *uniform* algorithms circuits implies that ZPEXP != BPP. If MCSP is in BPP, then statistical security and computational security for IO are equivalent. To the best of our knowledge, this is the first consequence of strong circuit lower bounds from the existence of an IO. The results are obtained via a construction of an optimal universal distinguisher, computable in randomized polynomial time with access to the MCSP oracle, that will distinguish any two circuit-samplable distributions with the advantage that is the statistical distance between these two distributions minus some negligible error term. This is our main technical contribution. As another application, we get a simple proof of the result by Allender and Das (Inf. Comput., 2017) that SZK is contained in BPP^MCSP.