Crypto Seminar

Thursday, July 15, 2021 - 4:30pm to 5:30pm


Virtual Presentation - ET Remote Access - Zoom


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.

Additional Reading

Zoom Participation. See announcement.

Event Website:

For More Information, Contact:


Seminar Series