אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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 EUROCRYPT’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.