Fine-Grained Complexity in a World Without Cryptography

Josh Alman, Yizhi Huang, Kevin Yeo

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 \(\textbf{P}\) such as \(k\text {-}\textsf{SUM}\) or \(\textsf{Zero}\text {-}k\text {-}\textsf{Clique}\). The ultimate hope is that fine-grained cryptography could still be viable even if all current cryptographic assumptions are false, such as if \(\textbf{P} = \textbf{NP}\) or if we live in Pessiland where one-way functions do not exist.
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