ECCC-Report TR17-063https://eccc.weizmann.ac.il/report/2017/063Comments and Revisions published for TR17-063en-usMon, 10 Apr 2017 21:49:12 +0300
Paper TR17-063
| Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions |
Benny Applebaum
https://eccc.weizmann.ac.il/report/2017/063The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness means that the number of satisfying assignments is not much smaller than the number of ``almost-satisfying'' assignments. We further show that the latter (``smooth-ETH'') assumption follows from the exponential hardness of solving constraint satisfaction problems over well-studied distributions, and, more generally, from the existence of any exponentially-hard locally-computable one-way function. This confirms a conjecture of Dinur (ECCC 2016).
We also prove an analogous result in the cryptographic setting. Namely, we show that the existence of exponentially-hard locally-computable pseudorandom generator with linear stretch (el-PRG) follows from the existence of an exponentially-hard locally-computable ``almost regular'' one-way functions.
None of the above assumptions (gap-ETH and el-PRG) was previously known to follow from the hardness of a search problem. Our results are based on a new construction of general (GL-type) hardcore functions that, for any exponentially-hard one-way function, output linearly many hardcore bits, can be locally computed, and consume only a linear amount of random bits. We also show that such hardcore functions have several other useful applications in cryptography and complexity theory.Mon, 10 Apr 2017 21:49:12 +0300https://eccc.weizmann.ac.il/report/2017/063