2026-07-21T23:34:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15518 2024-03-06T10:55:29Z ddc:004 open_access

One-Way Functions and a Conditional Variant of MKTP Allender, Eric Cheraghchi, Mahdi Myrisiotis, Dimitrios Tirumala, Harsha Volkovich, Ilya Kolmogorov complexity KT Complexity Minimum KT-complexity Problem MKTP Conditional KT Complexity Minimum Conditional KT-complexity Problem McKTP one-way functions OWFs average-case hardness pseudorandom generators PRGs pseudorandom functions PRFs distinguishers learning algorithms NP-completeness reductions 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 recently-announced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eric Allender and Mahdi Cheraghchi and Dimitrios Myrisiotis and Harsha Tirumala and Ilya Volkovich 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.7 urn:nbn:de:0030-drops-155181 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode