## On the Cryptographic Hardness of Finding a Nash Equilibrium

by Nir Bitansky, Omer Paneth, and Alon Rosen

#### Oded's comments

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.)

#### The original abstract

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.

Back to
list of Oded's choices.