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:
- Average-case PPAD hardness (and even average-case SVL hardness) does not
imply any form of cryptographic hardness (not even one-way functions).
- Average-case SVL hardness cannot be based either on standard
cryptographic assumptions or on average case PPAD hardness (and is thus not
essential for PPAD hardness).
- Any attempt for basing the average-case hardness of source-or-sink on
standard cryptographic assumptions must result in instances with a nearly
exponential number of solutions.
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.