TFNP and Cryptography: An Interplanetary Tour of Impagliazzo's Worlds

The hardness of total search problems (search problems where every instance has a solution) appears inherently related to cryptography: we do not know how to base cryptography on hardness of an NP-complete problem, and TFNP is (most would believe) a non-complete subclass of NP. Another suggestive connection is that one-way functions and TFNP hardness are the two possible consequences of the existence of hard "promise true" search problems (those where the sampler always outputs solvable instances). 

This talk will present a lay-of-the-land of the relatively new but burgeoning field of TFNP-and-crpyto. Our tour will be of an interplanetary nature, as we visit each of Impagliazzo's possible "worlds"; even though these planets are shrouded in atmospheric clouds that obscure their surface, in our fly-by we will see what is known about total hardness in each one. I hope to convince you that TFNP-crypto is interesting and possibly useful: it may be an avenue to find new assumptions for crypto, or to prove implications between crypto primitives and/or NP hardness-- that is, to conclude that some of the planets we thought we'd seen were not planets at all, but mirages. 

This talk is based on multiple papers and an ongoing class on the topic: https://dmitropolsky.github.io/teaching/6261/