Abstract
Let MK^tP[s] be the set of strings x such that K^t(x) \leq s(|x|), where K^t(x) denotes the t-bounded Kolmogorov complexity of the truthtable described by x. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every \varepsilon>0, polynomial t(n) \geq (1+\varepsilon)n, and every ``nice'' class F of super-polynomial functions, the following are equivalent (w.r.t. uniform or non-uniform attackers):
- the existence of some function T \in F such that T-hard one-way function (OWF) exists;
- the existence of some function T \in F such that MK^tP[T^{-1}] is mildly average-case hard with respect to sublinear-time algorithms (with running-time n^{\delta} for some 0<\delta<1).
For instance, existence of subexponentially-hard (resp. quasi-polynomially-hard) OWFs is equivalent to mild average-case hardness of MK^tP[\poly\log n] (resp. MK^tP[2^{O(\sqrt{\log n})})]) w.r.t. sublinear-time algorithms.