talk Monday 05.19 existence of public key cryptography, characterization using Kolmogorov complexity
15 views
Skip to first unread message
Bruno Bauwens
May 16, 2025, 10:26:01 AMMay 16
to Kolmogorov seminar on complexity
Hi,
Monday, at 16:30 CET or 18:30 MSK, I will continue my talk about the Kolmogorov complexity characterization of secret key agreement.
Ball, Liu, Mazor and Pass [BLMP23] proved that the existence of key-agreement protocols is equivalent to a certain estimate of interactive Kolmogorov complexity being in ioBPP. In the previous talk we stated the problem, explained that this estimation problem is decidable, and proved the backward impliciation (in the contra-positive, breaking a specific protocol provides an ioBPP algorithm for the estimation problem). In this talk we will briefly repeat everything and prove the forward implication (again in the contra-positive, with an ioBPP algorithm of the estimation problem we can break each protocol).
Zoom: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09
Notes: https://arxiv.org/pdf/2504.16311
The previous talk: https://www.youtube.com/watch?v=D1GdCXak0Nw
You received this message because you are subscribed to the mailinglist: Kolmogorov seminar on complexity.
To unsubscribe, write to: kolmogorov-seminar-on-...@googlegroups.com.
To view or modify settings: https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/80uS0H686g12-0TaHc6qgfOoJrHVHfWy_OEMdh8Vwi5tw8pDB2ncGs4qG_MhRRg9DRwKAVSjoEsQh7rWCx_wQi_yVgDLF_3yfD5LFRDwEvU%3D%40proton.me.
Monday, at 16:30 CET or 18:30 MSK, I will continue my talk about the Kolmogorov complexity characterization of secret key agreement.
Ball, Liu, Mazor and Pass [BLMP23] proved that the existence of key-agreement protocols is equivalent to a certain estimate of interactive Kolmogorov complexity being in ioBPP. In the previous talk we stated the problem, explained that this estimation problem is decidable, and proved the backward impliciation (in the contra-positive, breaking a specific protocol provides an ioBPP algorithm for the estimation problem). In this talk we will briefly repeat everything and prove the forward implication (again in the contra-positive, with an ioBPP algorithm of the estimation problem we can break each protocol).
Zoom: https://u-bordeaux-fr.zoom.us/j/88402787361?pwd=WktCdEhBT3pXN0pLUGg4Z3RuMlpsQT09
Notes: https://arxiv.org/pdf/2504.16311
The previous talk: https://www.youtube.com/watch?v=D1GdCXak0Nw
You received this message because you are subscribed to the mailinglist: Kolmogorov seminar on complexity.
To unsubscribe, write to: kolmogorov-seminar-on-...@googlegroups.com.
To view or modify settings: https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/80uS0H686g12-0TaHc6qgfOoJrHVHfWy_OEMdh8Vwi5tw8pDB2ncGs4qG_MhRRg9DRwKAVSjoEsQh7rWCx_wQi_yVgDLF_3yfD5LFRDwEvU%3D%40proton.me.
Nikolay Vereshchagin
May 16, 2025, 10:38:06 AMMay 16
to brba...@gmail.com, Kolmogorov seminar on complexity
It is 17:30 CEST (Paris time), and not 16:30!
--
Вы получили это сообщение, поскольку подписаны на группу Kolmogorov seminar on complexity.
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес kolmogorov-seminar-on-...@googlegroups.com.
Чтобы посмотреть обсуждение, перейдите по ссылке https://groups.google.com/d/msgid/kolmogorov-seminar-on-complexity/aCdK81LN9twiFeID%40brunob-GL613.
Н.В.
Reply all
Reply to author
Forward
0 new messages