Till innehåll på sidan

Rafael Pass: Connections between Cryptography and Kolmogorov Complexity

Tid: To 2023-10-26 kl 13.00

Plats: KTH, Rum 1537, Lindstedstvägen 3

Medverkande: Rafael Pass (Cornell and Tel Aviv University)

Exportera till kalender


Whether one-way functions (OWFs) exist is the most important outstanding problem in Cryptography. We will survey a recent thread of work showing the equivalence of the existence of OWFs and 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.

The talk aims to be self-contained and does not assume prior knowledge of Cryptography or Kolmogorov Complexity.

Mostly based on joint works with Yanyi Liu.