Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

by Alon Rosen, Gil Segev, and Ido Shahaf

Oded's comments

I have a "persnal stack" here: Noam Nisan ask me this question many years ago. Actually, he kind of assumed that the answer is positive, and wanted me to prove it. I failed, as in past cases when Noam asked me a question...

The original abstract

See ECCC TR16-059.

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only known source for average-case PPAD hardness.

Central in the study of obfuscation-based PPAD hardness is the sink-of-verifiable-line (SVL) problem, an intermediate step in constructing hard-on-average instances of the PPAD-complete problem source-or-sink. Within the framework of black-box reductions we prove the following results:

Taken together, our results imply that while it may still be possible to base average-case PPAD hardness on standard cryptographic assumptions, any black-box attempt must significantly deviate from the obfuscation-based approach: It cannot go through the SVL problem, and it must result in source-or-sink instances with a nearly-exponential number of solutions.
Back to list of Oded's choices.