TR23-079 Authors: Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Publication: 1st June 2023 03:00

Downloads: 356

Keywords:

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:

\begin{itemize}

\item If there exists a perfect (imperfect) $IO$ that is computationally secure against nonuniform polynomial-size circuits, then for all $k \in \mathbb{N}$: $NP \cap ZPP^{MCSP} \not \subseteq SIZE[n^k]$ ($MA \cap ZPP^{MCSP} \not \subseteq SIZE[n^k]$).

\item In addition, if there exists a perfect $IO$ that is computationally secure against nonuniform polynomial-size circuits, then $NEXP \cap ZPEXP^{MCSP} \not \subseteq P/poly.$

\item If $MCSP \in BPP$, then statistical security and computational security for $IO$ are equivalent.

\item If computationally-secure perfect $IO$ exists, then $MCSP \in BPP$ iff $NP = ZPP$.

\item If computationally-secure perfect $IO$ exists, then $ZPEXP \neq BPP$.

\end{itemize}

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 \emph{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 immediate application, we get a simple proof of the result by Allender and Das (Inf. Comput., 2017) that $SZK \subseteq BPP^{MCSP}$.