Interactive Kolmogorov Complexity and Key Agreement - Simplified Proof

In this 2-hour lecture from the Kolmogorov Seminar on computational and descriptional complexity, Bruno Bauwens presents a simplified proof of the equivalence between key-agreement protocols and Kolmogorov complexity. Explore the cryptographic conjecture that there exist protocols where Alice and Bob can exchange messages to obtain the same string x with high probability, while a time-bounded adversary fails to guess this key with probability 1-1/n^c for all c. Learn about the 2023 work by Ball, Liu, Mazor and Pass that formulated this conjecture using Kolmogorov complexity ("Kolmogorov goes to cryptomania"), and understand the simplified proof of this equivalence presented by Bauwens. This lecture is part of the historic Kolmogorov seminar series founded by Andrey Kolmogorov himself around 1979.