Paper 2026/2748

TFNP in the Random Oracle Model

Abstract

We determine which major TFNP classes are hard in the random oracle model (ROM). Prior work establishes average-case hardness of highly structured subclasses of TFNP from strong cryptographic assumptions such as LWE and indistinguishability obfuscation. It is not known whether weaker assumptions such as one-way functions imply hardness of any of the standard TFNP subclasses, even in the worst case. The ROM, where all parties have query access to a random function, lies, morally, between these two regimes: a random function is one-way, but public-key cryptography cannot be built from it in a black-box way. We refer to this setting as \emph{Romantica}. Our first result settles a long-standing open problem: PPAD, the class of total search problems reducible to finding a Nash equilibrium, is hard on average in Romantica. Combined with the known hardness of PLS (local search), this gives average-case hardness of EoPL = PPAD \cap PLS. In contrast, we show that UEoPL can be solved in Romantica with polynomially many oracle queries by a computationally unbounded solver, a sharp distinction between EoPL and UEoPL. This resolves the black-box hardness landscape of all major TFNP classes in Romantica. Finally, we initiate the study of separations between TFNP subclasses in Romantica: PWPP and PPA do not reduce to PLS under \emph{public-coin} reductions.