ECCC-Report TR21-009https://eccc.weizmann.ac.il/report/2021/009Comments and Revisions published for TR21-009en-usSat, 06 Feb 2021 17:16:04 +0200
Comment 1
| One-way Functions and Partial MCSP |
Eric Allender,
Mahdi Cheraghchi,
Dimitrios Myrisiotis,
Harsha Tirumala,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2021/009#comment1Mikito Nanashima and Hanlin Ren reported to us bugs in the proofs of Lemma 4.3 and Lemma 4.4, respectively.
Thank you very much! We are now working on fixing these bugs.Sat, 06 Feb 2021 17:16:04 +0200https://eccc.weizmann.ac.il/report/2021/009#comment1
Paper TR21-009
| One-way Functions and Partial MCSP |
Eric Allender,
Mahdi Cheraghchi,
Dimitrios Myrisiotis,
Harsha Tirumala,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2021/009One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some NP-complete problem. In this paper, we make progress on this question by studying a polynomially-sparse variant of Partial Minimum Circuit Size Problem (Partial MCSP), which we call Sparse Partial MCSP, as follows.
1. First, we prove that if Sparse Partial MCSP is zero-error average-case hard on a polynomial fraction of its instances, then there exist OWFs.
2. Then, we observe that Sparse Partial MCSP is NP-complete under polynomial-time deterministic reductions. That is, there are NP-complete problems whose average-case hardness implies the existence of OWFs.
3. Finally, we prove that the existence of OWFs implies the nontrivial zero-error average-case hardness of Sparse Partial MCSP.
Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem.Mon, 01 Feb 2021 23:54:03 +0200https://eccc.weizmann.ac.il/report/2021/009