Stanford Security Seminar

Rafael Pass

Abstract:

We prove the equivalence of two fundamental problems in the theory of computing. For every polynomial t(n)>2n, the following are equivalent:

(i) Cryptographic one-way functions exists;

(ii) 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.

Based on joint work with Yanyi Liu. https://eccc.weizmann.ac.il/report/2020/052/

Time and Place