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: