Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue ACM Transactions on Computation Theory Année : 2024

Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

Résumé

It is known that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings x and y is equal to the length of the longest shared secret key that two parties can establish via a probabilistic protocol with interaction on a public channel, assuming that the parties hold as their inputs x and y respectively. We determine the worst-case communication complexity of this problem for the setting where the parities can use private sources of random bits. We show that for some pairs x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key whose size is much smaller than the mutual information between x and y. On the other hand, we discuss examples of x, y such that the communication complexity of the protocol declines gradually with the size of the resulting secret key. The proof of the main result uses spectral properties of appropriate graphs and the expander mixing lemma, as well as information theoretic inequalities.
Fichier principal
Vignette du fichier
2004.13411v5.pdf (396.98 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-02558566 , version 1 (29-04-2020)
lirmm-02558566 , version 2 (11-05-2024)

Licence

Identifiants

Citer

Emirhan Gürpιnar, Andrei Romashchenko. Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory. ACM Transactions on Computation Theory, In press, ⟨10.1145/3665163⟩. ⟨lirmm-02558566v2⟩
176 Consultations
75 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More