Santhanam, Rahul
Pseudorandomness and the Minimum Circuit Size Problem
Abstract
We explore the possibility of basing oneway functions on the averagecase hardness of the fundamental Minimum Circuit Size Problem (MCSP[s]), which asks whether a Boolean function on n bits specified by its truth table has circuits of size s(n).
1) (Pseudorandomness from ZeroError AverageCase Hardness) We show that for a given size function s, the following are equivalent: Pseudorandom distributions supported on strings describable by s(O(n))size circuits exist; Hitting sets supported on strings describable by s(O(n))size circuits exist; MCSP[s(O(n))] is zeroerror averagecase hard. Using similar techniques, we show that Feige’s hypothesis for random kCNFs implies that there is a pseudorandom distribution (with constant error) supported entirely on satisfiable formulas. Underlying our results is a general notion of semantic sampling, which might be of independent interest.
2) (A New Conjecture) In analogy to a known universal construction of succinct hitting sets against arbitrary polynomialsize adversaries, we propose the Universality Conjecture: there is a universal construction of succinct pseudorandom distributions against arbitrary polynomialsize adversaries. We show that under the Universality Conjecture, the following are equivalent: Oneway functions exist; Natural proofs useful against subexponential size circuits do not exist; Learning polynomialsize circuits with membership queries over the uniform distribution is hard; MCSP[2^(ε n)] is zeroerror hard on average for some ε > 0; Cryptographic succinct hitting set generators exist.
3) (NonBlackBox Results) We show that for weak circuit classes ℭ against which there are natural proofs [Alexander A. Razborov and Steven Rudich, 1997], pseudorandom functions secure against polysize circuits in ℭ imply superpolynomial lower bounds in P against polysize circuits in ℭ. We also show that for a certain natural variant of MCSP, there is a polynomialtime reduction from approximating the problem well in the worst case to solving it on average. These results are shown using nonblackbox techniques, and in the first case we show that there is no blackbox proof of the result under standard crypto assumptions.
BibTeX  Entry
@InProceedings{santhanam:LIPIcs:2020:11753,
author = {Rahul Santhanam},
title = {{Pseudorandomness and the Minimum Circuit Size Problem}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {68:168:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11753},
URN = {urn:nbn:de:0030drops117532},
doi = {10.4230/LIPIcs.ITCS.2020.68},
annote = {Keywords: Minimum Circuit Size Problem, Pseudorandomness, Averagecase Complexity, Natural Proofs, Universality Conjecture}
}
06.01.2020
Keywords: 

Minimum Circuit Size Problem, Pseudorandomness, Averagecase Complexity, Natural Proofs, Universality Conjecture 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 