The Taub Faculty of Computer Science Events and Talks

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. Short bio: Rafael Pass graduated from MIT in 2006 and has since been a faculty member in the Computer Science Department at Cornell University. In 2013, he joined the newly founded Cornell Tech campus in New York city. His research interests are in Cryptography and its connections to Complexity Theory and Game Theory. He is the recipient of the NSF Career Award in 2008, the AFOSR Young Investigator Award in 2010, the Google Faculty award in 2015 and was named a Microsoft Faculty Fellow in 2009, a Sloan Research Fellow in 2011, and a JP Morgan Faculty fellow in 2020.