The class PPAD is build around the End-Of-The-Path problem (i.e., PPAD was defined as the set of problems reducible to EOFP). The input to EOTP is (1) a collection of directed paths and cycles presented (implicitly) by circuits that compute the successor and predecessor vertices, and (2) a source of the di-graph. The desired output is any sink or other source (i.e., a vertex that is at the end of some path, but is not the vertex given as input in (2)).
The existence of a ("virtual black-box") circuit obfuscation implies that EOTP is hard on the average-case, since such obfuscators can be applied to a pseudoarmdom permutation (which is ``cut'' at a hidden point). It is far less obvious that indistinguishability obfuscation (IO) suffices for such a hardness result (via a different construction), but given the flood of consequences of IO this is not as surprising as it would have been a few years ago. (Needless to say, surprise is not what matters, but rather the importance of the result.)
We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is known to be complete.
Previous proposals for basing PPAD-hardness on program obfuscation considered a strong "virtual black-box" notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps.
Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.