Thursday, July 15, 2021 - 4:30pm to 5:30pm
Location:Virtual Presentation - ET Remote Access - Zoom
Speaker:YANYI LIU, Cornell University /YANYI%20LIU
On One-way Functions and Kolmogorov Complexity
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.
Zoom Participation. See announcement.