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.ITCS.2020.68
URN: urn:nbn:de:0030-drops-117532
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11753/
Go to the corresponding LIPIcs Volume Portal

Santhanam, Rahul

Pseudorandomness and the Minimum Circuit Size Problem

pdf-format:
LIPIcs-ITCS-2020-68.pdf (0.6 MB)

Abstract

We explore the possibility of basing one-way functions on the average-case 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 Zero-Error Average-Case 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 zero-error average-case hard. Using similar techniques, we show that Feige’s hypothesis for random k-CNFs 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 polynomial-size adversaries, we propose the Universality Conjecture: there is a universal construction of succinct pseudorandom distributions against arbitrary polynomial-size adversaries. We show that under the Universality Conjecture, the following are equivalent: One-way functions exist; Natural proofs useful against sub-exponential size circuits do not exist; Learning polynomial-size circuits with membership queries over the uniform distribution is hard; MCSP[2^(ε n)] is zero-error hard on average for some ε > 0; Cryptographic succinct hitting set generators exist.
3) (Non-Black-Box 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 poly-size circuits in ℭ imply superpolynomial lower bounds in P against poly-size circuits in ℭ. We also show that for a certain natural variant of MCSP, there is a polynomial-time reduction from approximating the problem well in the worst case to solving it on average. These results are shown using non-black-box techniques, and in the first case we show that there is no black-box 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:1--68:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11753},
  URN =		{urn:nbn:de:0030-drops-117532},
  doi =		{10.4230/LIPIcs.ITCS.2020.68},
  annote =	{Keywords: Minimum Circuit Size Problem, Pseudorandomness, Average-case Complexity, Natural Proofs, Universality Conjecture}
}

Keywords: Minimum Circuit Size Problem, Pseudorandomness, Average-case Complexity, Natural Proofs, Universality Conjecture
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

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