2026-08-08T20:18:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18856 2024-03-06T11:02:45Z ddc:004 open_access

Synergy Between Circuit Obfuscation and Circuit Minimization Impagliazzo, Russell Kabanets, Valentine Volkovich, Ilya Minimal Circuit Size Problem (MCSP) Circuit Lower Bounds Complexity Classes Indistinguishability Obfuscation Separation of Classes Statistical Distance We study close connections between Indistinguishability Obfuscation (IO) and the Minimum Circuit Size Problem (MCSP), and argue that efficient algorithms/construction for MCSP and IO create a synergy. Some of our main results are: - If there exists a perfect (imperfect) IO that is computationally secure against nonuniform polynomial-size circuits, then for all k ∈ ℕ: NP ∩ ZPP^{MCSP} ⊈ SIZE[n^k] (MA ∩ ZPP^{MCSP} ⊈ SIZE[n^k]). - In addition, if there exists a perfect IO that is computationally secure against nonuniform polynomial-size circuits, then NEXP ∩ ZPEXP^{MCSP} ⊈ P/poly. - If MCSP ∈ BPP, then statistical security and computational security for IO are equivalent. - If computationally-secure perfect IO exists, then MCSP ∈ BPP iff NP = ZPP. - If computationally-secure perfect IO exists, then ZPEXP ≠ BPP. 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 immediate application, we get a simple proof of the result by Allender and Das (Inf. Comput., 2017) that SZK ⊆ BPP^{MCSP}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Russell Impagliazzo and Valentine Kabanets and Ilya Volkovich 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.31 urn:nbn:de:0030-drops-188569 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.31 eng https://creativecommons.org/licenses/by/4.0/legalcode