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^{\epsilon n}$] is zero-error hard on average for some $\epsilon > 0$; Cryptographic succinct hitting set generators exist.
3. (Non-Black-Box Results) We show that for weak circuit classes C against which there are natural proofs [Razborov-Rudich97], pseudorandom functions secure against poly-size circuits in C imply superpolynomial lower bounds in P against poly-size circuits in C. 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.
