Common information in well-mixing graphs and applications to information-theoretic cryptography - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2024

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

Abstract

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 and versions

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

Identifiers

Cite

Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov. Common information in well-mixing graphs and applications to information-theoretic cryptography. 2024. ⟨lirmm-04572079⟩
0 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More