Lecture: "Cryptography from the hardness of Olmogorov complexity"

Professor Rafael Pass, Department of Computer Science,
Cornell University and Cornell Tech, New York, USA 

07 November 2021, 11:10 

Professor Rafael Pass is ​2021/2022 IAS Distinguished Scholars of the Mortimer and Raymond Sackler Institute of Advanced Studies.



Whether one-way functions (OWFs) exist is the most important outstanding problem in Cryptography. We will survey a recent thread of work (Liu-Pass, FOCS'20, Liu-Pass, STOC'21, Liu-Pass, Crypto'21) showing the equivalence of the existence of OWFs and (mild) average-case hardness of various problems related to time-bounded Kolmogorov complexity that date back to the 1960s.
These results yield the first natural, and well-studied, computational problems characterizing the feasibility of the central private-key primitives and protocols in Cryptography.
Based on joint works with Yanyi Liu.

Tel Aviv University makes every effort to respect copyright. If you own copyright to the content contained
here and / or the use of such content is in your opinion infringing, Contact us as soon as possible >>