Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory

• Published in: ACM transactions on computation theory 2024-09, Vol.16 (3), p.1-37, Article 13
• Main Authors: Gürpιnar, Emirhan, Romashchenko, Andrei
• Format: Article
• Language: English
• Subjects: Communication complexity; Computational Complexity; Computer Science; Discrete Mathematics; Expander graphs and randomness extractors; Information Theory; Information-theoretic techniques; Mathematics; Mathematics of computing; Randomness, geometry and discrete structures; Security and privacy; Theory of computation
• ISSN: 1942-3454; 1942-3462
• DOI: 10.1145/3665163

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 parties can use private sources of random bits. We show that for some x, y the communication complexity of the secret key agreement does not decrease even if the parties have to agree on a secret key, the size of which is much smaller than the mutual information between x and y. However, we discuss a natural class of x, y such that the communication complexity of the protocol declines gradually with the size of the derived secret key. The proof of the main result uses the spectral properties of appropriate graphs and the expander mixing lemma, as well as information-theoretic techniques, including constraint information inequalities and Muchnik’s conditional descriptions. A preliminary version of this article was published in the proceedings of MFCS 2020. In the present version, we give full proofs of all theorems and get rid of the assumption that the number of random bits used in the communication protocols is polynomial.