Can PPAD Hardness be Based on Standard Cryptographic Assumptions?
We consider the question of whether 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
- PDF / 467,829 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 224 Views
Efi Arazi School of Computer Science, IDC, Herzliya, Israel [email protected] 2 School of Computer Science and Engineering, Hebrew University of Jerusalem, 91904 Jerusalem, Israel {segev,ido.shahaf}@cs.huji.ac.il
Abstract. We consider the question of whether 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 PPAD hardness. Central in the study of obfuscation-based PPAD hardness is the sinkof-verifiable-line (SVL) problem, an intermediate step in constructing 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 SVL hardness) does not imply any form of cryptographic hardness (not even one-way functions). Moreover, even when assuming the existence of one-way functions, average-case PPAD hardness (and, again, even SVL hardness) does not imply any public-key primitive. Thus, strong cryptographic assumptions (such as obfuscation-related ones) are not essential for average-case PPAD hardness. – Average-case SVL hardness cannot be based either on standard cryptographic assumptions or on average-case PPAD hardness. In particular, average-case SVL hardness is not essential for average-case PPAD hardness. – Any attempt for basing the average-case hardness of the PPADcomplete problem source-or-sink on standard cryptographic assumptions must result in instances with a nearly-exponential number of solutions. This stands in striking contrast to the obfuscationbased approach, which results in instances having a unique solution. Taken together, our results imply that it may still be possible to base PPAD hardness on standard cryptographic assumptions, but any such black-box attempt must significantly deviate from the obfuscationbased approach: It cannot go through the SVL problem, and it must result in source-or-sink instances with a nearly-exponential number of solutions.
c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part II, LNCS 10678, pp. 747–776, 2017. https://doi.org/10.1007/978-3-319-70503-3_25
748
1
A. Rosen et al.
Introduction
In recent years there has been increased interest in the computational complexity of finding a Nash equilibrium. Towards this end, Papadimitriou defined the complexity class PPAD, which consists of all TFNP problems that are polynomialtime reducible to the source-or-sink problem [31].1 Papadimitriou showed that the problem of finding a Nash equilibrium is reducible to source-or-sink, and thus belongs to PPAD. He also conjectured that there exists a reduction in the opposite direction, and this was proved by Daskalakis, Goldberg and Papadimitriou [18], and by Chen, Deng and Teng [11]. Thus, to support the belief that finding a Nash equilibrium may indeed be
Data Loading...
