arXiv Open Access 2024

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

Geoffroy Caillat-Grenier Andrei Romashchenko Rustam Zyavgarov

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.IT cs.DM

Penulis (3)

Geoffroy Caillat-Grenier

Andrei Romashchenko

Rustam Zyavgarov

Format Sitasi

APA MLA BibTeX

Caillat-Grenier, G., Romashchenko, A., Zyavgarov, R. (2024). Common information in well-mixing graphs and applications to information-theoretic cryptography. https://arxiv.org/abs/2405.05831

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓