We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.

1) Obfuscation can serve as a general-purpose *worst-case to average-case reduction*, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worst-case hardness assumptions beyond P \neq NP, and (ii) leveraging *worst-case* hardness reductions, either proved by traditional complexity-theoretic methods or facilitated further by cryptography.

Concretely, our results include:
- Optimal Hardness. Assuming sub-exponential indistinguishability obfuscation (iO), we give fine-grained worst-case to average case reductions for circuit-SAT. In particular, if finding an NP-witness requires nearly brute-force time in the worst case, then the same is true for some efficiently sampleable distribution. In fact, we show that under these assumptions, there exist families of one-way functions with optimal time-probability security tradeoffs. Under an additional, stronger assumption -- the optimal non-deterministic hardness of refuting circuit-SAT -- we construct additional cryptographic primitives such as PRGs and public-key encryption that have such optimal time-advantage security tradeoffs.

- Direct Product Hardness. Again assuming iO and optimal non-deterministic hardness of SAT refutation, we show that the "(search) $k$-fold SAT problem" -- the computational task of finding satisfying assignments to $k$ circuit-SAT instances simultaneously -- has (optimal) hardness roughly $(T/2^n)^k$ for time $T$ algorithms. In fact, we build "optimally secure one-way product functions" (Holmgren-Lombardi, FOCS '18), demonstrating that optimal direct product theorems hold for some choice of one-way function family.

- Single-Input Correlation Intractability. Assuming either iO or LWE, we show a worst-case to average-case reduction for strong forms of single-input correlation intractability. That is, powerful forms of correlation-intractable hash functions exist provided that a collection of worst-case "correlation-finding" problems are hard.

- Non-interactive Proof of Quantumness. Assuming sub-exponential iO and OWFs, we give a non-interactive proof of quantumness based on the worst-case hardness of the white-box Simon problem. In particular, this proof of quantumness result does not explicitly assume quantum advantage for an average-case task.

To help prove our first two results, we show along the way how to improve the Goldwasser-Sipser "set lower bound" protocol to have communication complexity quadratically smaller in the multiplicative approximation error $\epsilon$.