  We prove that the equivalence of two fundamental problems in the theory of
computing. For every polynomial $t(n)\geq (1+\varepsilon)n, \varepsilon>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-\frac{1}{p(n)}$ 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.
