On One-way Functions and Kolmogorov Complexity (via Zoom)

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 exist;

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 Rafael Pass https://eccc.weizmann.ac.il/report/2020/052/

Bio: I am a second-year computer science PhD student at Cornell. I am interested in cryptography and theoretical computer science in general. I am extremely fortunate to be advised by Rafael Pass and Elaine Shi. Previously, I obtained my bachelor degree in computer science at Tsinghua University.