Common information in well-mixing graphs and applications to information-theoretic cryptography
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909777127276544 |
|---|---|
| author | Caillat-Grenier, Geoffroy Romashchenko, Andrei Zyavgarov, Rustam |
| author_facet | Caillat-Grenier, Geoffroy Romashchenko, Andrei Zyavgarov, Rustam |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_05831 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Common information in well-mixing graphs and applications to information-theoretic cryptography Caillat-Grenier, Geoffroy Romashchenko, Andrei Zyavgarov, Rustam Information Theory Discrete Mathematics 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. |
| title | Common information in well-mixing graphs and applications to information-theoretic cryptography |
| topic | Information Theory Discrete Mathematics |
| url | https://arxiv.org/abs/2405.05831 |