Random oracles show new hardness results for total search problems
TFNP in the Random Oracle Model
Computational Complexity
Summary
The paper studies how hard it is to solve certain guaranteed-to-have-solutions problems (called TFNP) when all parties can access a truly random function, known as the random oracle model. The authors solve a long-standing question by showing that a well-known class of problems related to finding equilibria, called PPAD, is on average hard to solve in this setting. They also draw new lines between subclasses of these problems, identifying what can and cannot be efficiently solved with such oracles. This advances the understanding of problem difficulty when only minimal cryptographic assumptions hold.
What this means in practice
- •For cryptosystem designers: Evaluate which total search problem classes remain hard when relying on minimal assumptions like random oracles for cryptographic constructions.
- •For complexity theorists: Use the identified separations between TFNP subclasses to guide proof techniques and complexity classifications in oracle settings.
A theory result. No direct application yet.
Authors
Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten, Daniel Mitropolsky, Toniann Pitassi, Artur Riazanov, Dmitry Sokolov, Tianqi Yang, Weiqiang Yuan
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.