On One-way Functions and Kolmogorov Complexity
Yanyi Liu, Rafael Pass
Abstract
We prove that the equivalence of two fundamental problems in the theory of computing. For every polynomial , 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sup> , is mildly hard-on-average (i.e., there exists a polynomial such that no PPT algorithm can compute K <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sup> , for more than a 1-[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.