Paper 2025/324

Fine-Grained Complexity in a World without Cryptography

Josh Alman, Columbia University
Yizhi Huang, Columbia University
Kevin Yeo, Columbia University, Google (United States)
Abstract

The study of fine-grained cryptography has proliferated in recent years due to its allure of potentially relying on weaker assumptions compared to standard cryptography. As fine-grained cryptography only requires polynomial gaps between the adversary and honest parties, it seems plausible to build primitives relying upon popular hardness assumptions about problems in such as - or --. The ultimate hope is that fine-grained cryptography could still be viable even if all current cryptographic assumptions are false, such as if or if we live in Pessiland where one-way functions do not exist. In our work, we consider whether this approach is viable by studying fine-grained complexity when all standard cryptographic assumptions are false. As our main result, we show that many popular fine-grained complexity problems are easy to solve in the average-case when one-way functions do not exist. In other words, many candidate hardness assumptions for building fine-grained cryptography are no longer options in Pessiland. As an example, we prove that the average-case - and -- conjectures are false for sufficiently large constant when no one-way functions exist. The average-case -- assumption was used to build fine-grained key-exchange by Lavigne et al. [CRYPTO'19]. One can also view the contrapositive of our result as providing an explicit construction of one-way functions assuming average-case hardness of - or -- for all constant . We also show that barriers for reductions in fine-grained complexity may be explained by problems in cryptography. First, we show that finding faster algorithms for computing discrete logarithms is equivalent to designing average-case equivalence between - and - (an extension of - to cyclic groups). In particular, finding such a reduction from - to - could potentially lead to breakthrough algorithms for the discrete logarithm, factoring, RSA and quadratic residuosity problems. Finally, we show that discrete logarithms with preprocessing may be reduced to the -- problem, and we present faster algorithms for average-case -- and --.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in EUROCRYPT 2025
Keywords
fine-grained complexityk-sumone-way function
Contact author(s)
josh @ cs columbia edu
yizhi @ cs columbia edu
kwlyeo @ cs columbia edu
History
2025-02-25: revised
2025-02-22: received
See all versions
Short URL
https://ia.cr/2025/324
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/324,
      author = {Josh Alman and Yizhi Huang and Kevin Yeo},
      title = {Fine-Grained Complexity in a World without Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/324},
      year = {2025},
      url = {https://eprint.iacr.org/2025/324}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.