yesterday's talk video
2 views
Skip to first unread message
Alexander Shen
Mar 11, 2025, 6:35:16 AMMar 11
to Kolmogorov seminar on complexity
https://youtu.be/D1GdCXak0Nw
2025-03-10:
Title: Existence of key-agreement, a Kolmogorov complexity
characterization.
Abstract:
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.
2025-03-10:
Title: Existence of key-agreement, a Kolmogorov complexity
characterization.
Abstract:
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.
Reply all
Reply to author
Forward
0 new messages