Fine-Grained Complexity in a World Without Cryptography

Josh Alman, Yizhi Huang, Kevin Yeo

TL;DR

This paper explores the implications of a world without one-way functions (OWFs) for fine-grained complexity, a field that aims to build cryptographic primitives with polynomial time gaps. The authors show that many popular fine-grained hardness assumptions, like k-SUM and Zero-k-Clique, actually become easy on average in such a world, undermining their use for constructing cryptographic primitives. They also reveal a surprising connection: efficient reductions between k-CYC/k-PROD and k-SUM are blocked by the difficulty of the discrete logarithm problem.

What Problem Does This Paper Address?

Modern cryptography relies on hard computational problems (like factoring or discrete logarithms) to ensure security. However, these assumptions are often unproven and could be false. Fine-grained complexity offers a potential alternative by relying on polynomial time gaps between efficient and inefficient algorithms for problems in P, aiming for security even if P=NP. This approach has led to constructions of cryptographic primitives like OWFs and key-exchange protocols based on the average-case hardness of problems like k-SUM and Zero-k-Clique.

The central question this paper addresses is: What happens to these fine-grained complexity assumptions if we live in a world where one-way functions (OWFs) do not exist? This is crucial because if OWFs don't exist, then many of the cryptographic constructions that rely on them would be broken. The authors investigate whether the presumed hardness of problems like k-SUM and Zero-k-Clique still holds in this "Pessiland" scenario, and what this implies for fine-grained cryptography.

Methods

The paper employs several key techniques:

  • Planting Algorithms: A core method involves "planting algorithms." These algorithms efficiently generate instances of a problem that are guaranteed to have a solution, and importantly, can also efficiently find that solution. This is used to construct instances with solutions that can be efficiently inverted.
  • Universal One-Way Functions (UOWFs): The authors leverage the concept of UOWFs. The existence of a UOWF is equivalent to the existence of OWFs. The paper shows that if OWFs don't exist, then certain functions (specifically, those generated by planting algorithms) become efficiently invertible. This invertibility is then used to show that the corresponding problems are easy on average.
  • Average-Case Reductions: The paper establishes reductions between problems. A key result shows that an efficient reduction from k-CYC (or k-PROD) to k-SUM would imply faster algorithms for discrete logarithms. This establishes a cryptographic barrier to proving equivalences between these problems.
  • Time-Space Trade-offs: For indexing problems, the authors present improved algorithms with better space-time trade-offs, building upon existing techniques like Hellman's algorithm for inverting random functions.

Datasets

Not discussed in the paper. The paper deals with theoretical computational problems and their hardness, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Fine-grained Hardness Collapses Without OWFs: The most striking insight is that many problems considered hard in fine-grained complexity (like k-SUM and Zero-k-Clique) become easy on average if OWFs don't exist. This directly challenges their use as the foundation for cryptographic primitives in such a world.
  • Discrete Logarithm as a Barrier: The paper reveals a surprising cryptographic barrier: efficient reductions between k-CYC/k-PROD and k-SUM are fundamentally limited by the difficulty of solving the discrete logarithm problem. This means proving these problems are equivalent would imply that discrete logarithms are easy, which is a major open problem in cryptography.
  • Pessiland is Simpler: The paper suggests that in a world without OWFs, the computational landscape for certain problems becomes significantly simpler, with average-case hardness assumptions failing.

Key Results

  • AVG-k-SUM and AVG-Zero-k-Clique are False Without OWFs: The paper proves that if OWFs do not exist, then the average-case k-SUM and Zero-k-Clique conjectures are false. This means there exist efficient algorithms to solve these problems on average.
  • Fast Algorithms for k-SUM/Zero-k-Clique: For infinitely many input sizes, the authors provide algorithms that solve k-SUM and Zero-k-Clique in linear time (O(n)) when OWFs do not exist, regardless of the value of k.
  • DLog Barrier for k-SUM/k-CYC Reductions: The paper shows that an efficient reduction from k-CYC (or k-PROD) to k-SUM would imply sub-exponential time algorithms for discrete logarithms, factoring, RSA, and quadratic residuosity. This establishes a strong barrier to proving equivalences between these problems.
  • Improved Algorithms for Indexing Problems: New algorithms for k-SUM-Index and k-CYC-Index are presented with better space-time trade-offs compared to previous worst-case algorithms.

Limitations and Future Work

  • Focus on Average-Case: The results primarily concern average-case hardness. While the paper discusses implications for worst-case scenarios, the direct algorithmic results are for the average case.
  • "Infinitely Many n": The existence of efficient algorithms is proven for "infinitely many n," which is a standard theoretical construct but doesn't guarantee efficiency for all input sizes.
  • Future Work: The paper suggests exploring the implications for other cryptographic primitives and assumptions. It also opens avenues for further investigation into the precise relationships between fine-grained problems and cryptographic hardness, particularly in the context of a world without OWFs. The connection between discrete logarithms and reductions between k-SUM and its variants is a significant area for future research.

Summary updated

BibTeX
@article{alman2025fine,
  author = {Josh Alman and Yizhi Huang and Kevin Yeo},
  title = {{Fine-Grained Complexity in a World Without Cryptography}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}

Loading related content...

Figure