On One-way Functions and Kolmogorov Complexity

We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n) ≥ (1 + ε)n, ε > 0, the following are equivalent:

• One-way functions exists (which in turn is equivalent to the existence of secure private-key encryption schemes, digital signatures, pseudorandom generators, pseudorandom functions, commitment schemes, and more);

• t-time bounded Kolmogorov Complexity, K t , is mildly hard-on-average (i.e., there exists a polynomial p(n) > 0 such that no PPT algorithm can compute K t , for more than a 1 -1

fraction of n-bit strings).

In doing so, we present the first natural, and well-studied, computational problem characterizing the feasibility of the central private-key primitives and protocols in Cryptography.