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 $P \neq 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 $\left(T / 2^{n}\right)^{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 $\varepsilon$.