Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity

Let MK t P[s] be the set of strings x such that K t (x) ≤ 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 ε > 0, polynomial t(n) ≥ (1 + ε)n, and every "nice" class F of super-polynomial functions, the following are equivalent:

• the existence of some function T ∈ F such that T -hard one-way functions (OWF) exists (with non-uniform security);

• the existence of some function T ∈ F such that MK t P[T -1 ] is mildly average-case hard with respect to sublinear-time non-uniform algorithms (with running-time n δ for some 0 < δ < 1). For instance, existence of subexponentially-hard (resp. quasi-polynomially-hard) OWFs is equivalent to mild average-case hardness of MK t P[poly log n] (resp. MK t P[2 O( √ log n) )]) w.r.t. sublineartime non-uniform algorithms. We additionally note that if we want to deduce T -hard OWFs where security holds w.r.t. uniform T -time probabilistic attackers (i.e., uniformly-secure OWFs), it suffices to assume sublinear time hardness of MK t P w.r.t. uniform probabilistic sublinear-time attackers. We complement this result by proving lower bounds that come surprisingly close to what is required to unconditionally deduce the existence of (uniformly-secure) OWFs: MK t P[poly log n] is worst-case hard w.r.t. uniform probabilistic sublinear-time algorithms, and MK t P[n -log n] is mildly average-case hard for all O(t(n)/n 3 )-time deterministic algorithms.