#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

10 March 2025, 16.30 CET = 18.30 Moscow time

Existence of key-agreement, a Kolmogorov complexity characterization.

Bruno Bauwens

In a key-agreement protocol, Alice and Bob have a natural number n, exchange messages, and obtain with high probability the same string x. A time bounded adversery listen to the messages and guesses the key x. A common conjecture in cryptography is that there exist protocols in which the adversary fails to guess the key with probability 1 - 1/n^c for all c. In 2023, Ball, Liu, Mazor and Pass gave an equivalent formulation of this conjecture using Kolmogorov complexity ("Kolmogorov goes to cryptomania"). We present a simple proof this equivalence.

➰ ВК