An Operational Characterization of Mutual Information in Algorithmic Information Theory
Autor: | Andrei Romashchenko, Marius Zimand |
---|---|
Přispěvatelé: | Systèmes complexes, automates et pavages (ESCAPE), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Centre National de la Recherche Scientifique (CNRS), Department of Computer and Information Sciences [Towson], Towson University [Towson, MD, United States], University of Maryland System-University of Maryland System, ANR-15-CE40-0016,RaCAF,Dépasser les frontières de l'aléatoire et du calculable(2015), Department of Computer and Information Sciences, University of Maryland System |
Jazyk: | angličtina |
Rok vydání: | 2018 |
Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences TheoryofComputation_MISCELLANEOUS Logarithm Computer science Computer Science - Information Theory Kolmogorov complexity 0102 computer and information sciences 02 engineering and technology Shared secret [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Computational Complexity (cs.CC) 01 natural sciences Artificial Intelligence 0202 electrical engineering electronic engineering information engineering communication complexity Communication complexity mutual information Randomness Computer Science::Databases Computer Science::Cryptography and Security Discrete mathematics Algorithmic information theory 000 Computer science knowledge general works Information Theory (cs.IT) information inequalities [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT] 020206 networking & telecommunications Mutual information 16. Peace & justice Computer Science - Computational Complexity secret key agreement 010201 computation theory & mathematics Hardware and Architecture Control and Systems Engineering Computer Science Tuple Software Information Systems |
Zdroj: | Journal of the ACM (JACM) Journal of the ACM (JACM), Association for Computing Machinery, 2019, 66 (5), pp.1-42. ⟨10.1145/3356867⟩ 45th International Colloquium on Automata, Languages, and Programming ICALP: International Colloquium on Automata, Languages, and Programming ICALP: International Colloquium on Automata, Languages, and Programming, Jul 2018, Prague, Czech Republic. pp.95:1-95:14, ⟨10.4230/LIPIcs.ICALP.2018.95⟩ |
ISSN: | 0004-5411 1557-735X |
DOI: | 10.4230/lipics.icalp.2018.95 |
Popis: | We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings $x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties, one having $x$ and the complexity profile of the pair and the other one having $y$ and the complexity profile of the pair, can establish via a probabilistic protocol with interaction on a public channel. For $\ell > 2$, the longest shared secret that can be established from a tuple of strings $(x_1, \ldots , x_\ell)$ by $\ell$ parties, each one having one component of the tuple and the complexity profile of the tuple, is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length, for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained. 39 pages, 2 figures. A brief version of this work has been presented at 45th International Colloquium on Automata, Languages, and Programming (ICALP), Prague, July 10-13, 2018 |
Databáze: | OpenAIRE |
Externí odkaz: |