License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.31
URN: urn:nbn:de:0030-drops-188569
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18856/
Go to the corresponding LIPIcs Volume Portal

Impagliazzo, Russell ; Kabanets, Valentine ; Volkovich, Ilya

Synergy Between Circuit Obfuscation and Circuit Minimization

pdf-format:
LIPIcs-APPROX31.pdf (0.9 MB)

Abstract

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

BibTeX - Entry

@InProceedings{impagliazzo_et_al:LIPIcs.APPROX/RANDOM.2023.31,
  author =	{Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya},
  title =	{{Synergy Between Circuit Obfuscation and Circuit Minimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18856},
  URN =		{urn:nbn:de:0030-drops-188569},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.31},
  annote =	{Keywords: Minimal Circuit Size Problem (MCSP), Circuit Lower Bounds, Complexity Classes, Indistinguishability Obfuscation, Separation of Classes, Statistical Distance}
}

Keywords: Minimal Circuit Size Problem (MCSP), Circuit Lower Bounds, Complexity Classes, Indistinguishability Obfuscation, Separation of Classes, Statistical Distance
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Issue Date: 2023
Date of publication: 04.09.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI