ECCC-Report TR16-059https://eccc.weizmann.ac.il/report/2016/059Comments and Revisions published for TR16-059en-usMon, 26 Oct 2020 13:04:09 +0200
Revision 2
| Can PPAD Hardness be Based on Standard Cryptographic Assumptions? |
Alon Rosen,
Gil Segev,
Ido Shahaf
https://eccc.weizmann.ac.il/report/2016/059#revision2We 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.Mon, 26 Oct 2020 13:04:09 +0200https://eccc.weizmann.ac.il/report/2016/059#revision2
Revision 1
| Can PPAD Hardness be Based on Standard Cryptographic Assumptions? |
Alon Rosen,
Gil Segev,
Ido Shahaf
https://eccc.weizmann.ac.il/report/2016/059#revision1We 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.Sun, 01 May 2016 07:48:01 +0300https://eccc.weizmann.ac.il/report/2016/059#revision1
Paper TR16-059
| Can PPAD Hardness be Based on Standard Cryptographic Assumptions? |
Alon Rosen,
Gil Segev,
Ido Shahaf
https://eccc.weizmann.ac.il/report/2016/059We 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.Thu, 14 Apr 2016 22:44:08 +0300https://eccc.weizmann.ac.il/report/2016/059