Rafael Pass: On One-way Functions and Kolmogorov Complexity

Friday, February 19, 2021 - 1:00pm to 2:30pm
Location: 
Please email dlehto@mit.edu for Zoom Link
Speaker: 
Rafael Pass
Seminar group: 
Cryptography and Information Security (CIS) Seminar
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 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
https://eccc.weizmann.ac.il/report/2020/052/