Rafael Pass: On One-way Functions and Kolmogorov Complexity

Friday, February 19, 2021 - 1:00pm to 2:30pm
Please email dlehto@mit.edu for Zoom Link
Rafael Pass
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.
Based on joint work with Yanyi Liu