Summary: One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Y. Liu and R. Pass [in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 722–735 (2021; Zbl 07765205)] 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 recently-announced results of H. Ren and R. Santhanam [LIPIcs – Leibniz Int. Proc. Inform. 200, Article 35, 58 p. (2021; Zbl 07711617)], we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.
For the entire collection see [Zbl 1482.68008].