Cryptography Meets Worst-case Complexity: Optimal Security and More From iO and Worst-case Assumptions

We study several problems in the intersection of cryptography and complexity theory based on the following highlevel 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 worstcase hardness assumptions beyond pneq N P, 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, 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 timeadvantage 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ⁿ)^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 'correlationfinding' problems are hard.•Non-interactive Proof of Quantumness. Assuming subexponential iO and OWFs, we give a non-interactive proof of quantumness based on the worst-case hardness of the whitebox 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 ϵ.