[Resource Topic] 2025/1087: Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions

Resource Foundations
1

Welcome to the resource topic for 2025/1087

Title:
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions

Authors: Rahul Ilango, Alex Lombardi

Abstract:

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 \mathsf{P}\neq \mathsf{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, we give fine-grained worst-case to average case reductions for circuit-SAT. In particular, if finding an \mathsf{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 i\mathcal O 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 i\mathcal O or \mathsf{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 \emph{worst-case} ``correlation-finding’’ problems are hard.

  • Non-interactive Proof of Quantumness. Assuming sub-exponential i\mathcal O 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.

ePrint: https://eprint.iacr.org/2025/1087

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .