Hirahara, Shuichi ;
Watanabe, Osamu
On Nonadaptive Security Reductions of Hitting Set Generators
Abstract
One of the central open questions in the theory of averagecase complexity is to establish the equivalence between the worstcase and averagecase complexity of the Polynomialtime Hierarchy (PH). One general approach is to show that there exists a PHcomputable hitting set generator whose security is based on some NPhard problem. We present the limits of such an approach, by showing that there exists no exponentialtimecomputable hitting set generator whose security can be proved by using a nonadaptive randomized polynomialtime 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 NPhard problem must use either an adaptive or nonblackbox reduction (unless the polynomialtime hierarchy collapses). To the best of our knowledge, this is the first result that shows limits of blackbox reductions from an NPhard problem to some form of a distributional problem in DistPH.
Based on our results, we argue that the recent worstcase to averagecase reduction of Hirahara (FOCS 2018 [Hirahara, 2018]) is inherently nonblackbox, without relying on any unproven assumptions. On the other hand, combining the nonblackbox reduction with our simulation technique of blackbox reductions, we exhibit the existence of a "nonblackbox 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:115:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12618},
URN = {urn:nbn:de:0030drops126182},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.15},
annote = {Keywords: hitting set generator, blackbox reduction, averagecase complexity}
}
11.08.2020
Keywords: 

hitting set generator, blackbox reduction, averagecase complexity 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 