Zero-knowledge ($ZK$) protocols are one of the most fundamental cryptographic primitives. Classic results in the 1980s established that one-way functions (OWFs) suffice for constructing $ZK$ for $NP$ (Goldreich-Micali-Wigderson [JACM'91], Naor [CRYPTO’89], Hastad et al. [SICOMP’99]). Moreover, OWFs are, in fact, necessary for $ZK$ for $NP$, due to the classic result of Ostrovsky and Wigderson [ISTCS'93], which was recently strengthened by Hirahara and Nanashima [STOC'24].
But for many applications of $ZK$, it suffices to consider a slight relaxation of the $ZK$ property where the simulator is allowed to run in super-polynomial time (Pass [Eurocrypt'03]). Surprisingly, the results of Ostrovsky and Wigderson break once we allow even a slightly inefficient simulator.
Indeed, a recent result by Baril and Haitner [CRYPTO'26] shows that, without efficient simulation, $ZK$ does not imply one-way functions in a black-box manner.
We show that two-message arguments with a (non-trivial) inefficient simulator imply the errorless average-case hardness of the Minimum Time-Bounded Kolmogorov Complexity Problem ($MKtP$) over the uniform distribution. The hardness of the same problem against two-sided error algorithms is known to imply OWFs (Liu and Pass, [FOCS'20]).
As far as we know, this result is the first complexity-theoretic consequence of $ZK$ with even just slightly super-polynomial-time simulation.