Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR21-009 | 9th November 2021 17:23

One-way Functions and a Conditional Variant of MKTP

RSS-Feed




Revision #3
Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
Accepted on: 9th November 2021 17:23
Downloads: 308
Keywords: 


Abstract:

One-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 natural $NP$-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows.

1. First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs.
2. Then, we observe that McKTP is $NP$-complete under polynomial-time randomized reductions.
3. Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP.

Thus the existence of OWFs is inextricably linked to the average-case hardness of this $NP$-complete problem. In fact, building on recent results of Ren and Santhanam (CCC 2021), we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.



Changes to previous version:

We edited the timeline of related papers (that appears in the Introduction), to make it more precise.


Revision #2 to TR21-009 | 19th October 2021 23:03

One-way Functions and a Conditional Variant of MKTP





Revision #2
Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
Accepted on: 19th October 2021 23:03
Downloads: 285
Keywords: 


Abstract:

One-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 natural $NP$-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows.

1. First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs.
2. Then, we observe that McKTP is $NP$-complete under polynomial-time randomized reductions.
3. Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP.

Thus the existence of OWFs is inextricably linked to the average-case hardness of this $NP$-complete problem. In fact, building on recent results of Ren and Santhanam (CCC 2021), we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.



Changes to previous version:

This is an updated version that incorporates feedback from our reviewers. Thank you!


Revision #1 to TR21-009 | 18th April 2021 06:38

One-way Functions and a Conditional Variant of MKTP





Revision #1
Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
Accepted on: 18th April 2021 06:38
Downloads: 449
Keywords: 


Abstract:

One-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 \emph{equivalent} to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some $\mathsf{NP}$-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows.

1. First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs.
2. Then, we observe that McKTP is $\mathsf{NP}$-complete under polynomial-time randomized reductions. That is, there \emph{are} $\mathsf{NP}$-complete problems whose average-case hardness implies the existence of OWFs.
3. Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP.

Thus the existence of OWFs is inextricably linked to the average-case hardness of this $\mathsf{NP}$-complete problem.



Changes to previous version:

We took care of the bugs found by Mikito Nanashima and Hanlin Ren. Thank you for your help!

Just as we were preparing to post this article, we were made aware that
Liu and Pass, working independently (and having seen the earlier version of our work, that had errors), now claim that a (slightly different) version of time-bounded conditional Kolmogorov complexity is

1. $\mathsf{NP}$-complete under polynomial-time randomized reductions, and
2. hard on average on a \emph{polynomial} fraction of its instances if and only if OWFs exist.

The main points of departure between the work by Liu and Pass and ours, are that Liu and Pass consider conditional $K^t$ complexity, while we consider conditional KT complexity, and that their work claims an \emph{equivalence} between the average-case hardness of an $\mathsf{NP}$-complete problem and the existence of OWFs.


Paper:

TR21-009 | 1st February 2021 23:40

One-way Functions and Partial MCSP


Abstract:

One-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.


Comment(s):

Comment #1 to TR21-009 | 6th February 2021 17:16

One-way Functions and Partial MCSP

Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich
Accepted on: 6th February 2021 17:16
Keywords: 


Comment:

Mikito 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.




ISSN 1433-8092 | Imprint