On Average-Case Hardness in \(\mathsf {TFNP}\) from One-Way Functions

The complexity class \(\mathsf {TFNP}\) consists of all \(\mathsf {NP}\) search problems that are total in the sense that a solution is guaranteed to exist for all instances. Over the years, this class has proved to illuminate surprising connections among several diverse subfields of mathematics like combinatorics, computational topology, and algorithmic game theory. More recently, we are starting to better understand its interplay with cryptography.