Title: On one-way functions and Kolmogorov complexity

Abstract: We prove the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n)>2n, the following are equivalent: Cryptographic one-way functions exists; The t-time bounded Kolmogorov Complexity problem is mildly hard-on-average. 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. Joint work with Yanyi Liu.

More information available at https://www.dcs.warwick.ac.uk/~igorcarb/complexity-meetings.html