Common information in well-mixing graphs and applications to information-theoretic cryptography - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2024

Common information in well-mixing graphs and applications to information-theoretic cryptography

Résumé

We study the connection between mixing properties for bipartite graphs and materialization of the mutual information in one-shot settings. We show that mixing properties of a graph imply impossibility to extract the mutual information shared by the ends of an edge randomly sampled in the graph. We apply these impossibility results to some questions motivated by information-theoretic cryptography. In particular, we show that communication complexity of a secret key agreement in one-shot setting is inherently uneven: for some inputs, almost all communication complexity inevitably falls on only one party.

Dates et versions

lirmm-04572079 , version 1 (10-05-2024)

Identifiants

Citer

Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov. Common information in well-mixing graphs and applications to information-theoretic cryptography. 2024. ⟨lirmm-04572079⟩
9 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More