License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.15
URN: urn:nbn:de:0030-drops-126182
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12618/
Go to the corresponding LIPIcs Volume Portal

Hirahara, Shuichi ; Watanabe, Osamu

On Nonadaptive Security Reductions of Hitting Set Generators

pdf-format:
LIPIcs-APPROX15.pdf (0.5 MB)

Abstract

One of the central open questions in the theory of average-case complexity is to establish the equivalence between the worst-case and average-case complexity of the Polynomial-time Hierarchy (PH). One general approach is to show that there exists a PH-computable hitting set generator whose security is based on some NP-hard problem. We present the limits of such an approach, by showing that there exists no exponential-time-computable hitting set generator whose security can be proved by using a nonadaptive randomized polynomial-time reduction from any problem outside AM ∩ coAM, which significantly improves the previous upper bound BPP^NP of Gutfreund and Vadhan (RANDOM/APPROX 2008 [Gutfreund and Vadhan, 2008]). In particular, any security proof of a hitting set generator based on some NP-hard problem must use either an adaptive or non-black-box reduction (unless the polynomial-time hierarchy collapses). To the best of our knowledge, this is the first result that shows limits of black-box reductions from an NP-hard problem to some form of a distributional problem in DistPH.
Based on our results, we argue that the recent worst-case to average-case reduction of Hirahara (FOCS 2018 [Hirahara, 2018]) is inherently non-black-box, without relying on any unproven assumptions. On the other hand, combining the non-black-box reduction with our simulation technique of black-box reductions, we exhibit the existence of a "non-black-box selector" for GapMCSP, i.e., an efficient algorithm that solves GapMCSP given as advice two circuits one of which is guaranteed to compute GapMCSP.

BibTeX - Entry

@InProceedings{hirahara_et_al:LIPIcs:2020:12618,
  author =	{Shuichi Hirahara and Osamu Watanabe},
  title =	{{On Nonadaptive Security Reductions of Hitting Set Generators}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12618},
  URN =		{urn:nbn:de:0030-drops-126182},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.15},
  annote =	{Keywords: hitting set generator, black-box reduction, average-case complexity}
}

Keywords: hitting set generator, black-box reduction, average-case complexity
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

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