Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SEPARATION OF CLASSES:
Reports tagged with Separation of classes:
TR23-079 | 31st May 2023
Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

Mutual Empowerment between Circuit Obfuscation and Circuit Minimization

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 ... more >>>




ISSN 1433-8092 | Imprint