On Cryptography and Kolmogorov Complexity

Whether secure Cryptography exists is one of the most important open problems in Computer Science: Cryptographic schemes today rely on unproven computational hardness assumption.

We will survey a recent thread of work (Liu-Pass,FOCS’20, Liu-Pass-STOC’21,.., Ball-Liu-Pass-Mazor, FOCS’23, Liu-Pass’EUROCRYPTO’24) showing *equivalences* between the existence of some of the most basic cryptographic primitives, and the hardness of various computational problems related to the notion of *time-bounded Kolmogorov Complexity* (dating back to the 1960s).

These results yield the first natural computational problems *characterizing* the feasibility of central primitives and protocols in Cryptography, as well as the first *unstructured* computational problems enabling public-key cryptography.

No prior knowledge of Cryptography or Kolmogorov complexity will be assumed.