Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR18-043 | 29th April 2019 21:02

#### An operational characterization of mutual information in algorithmic information theory

Revision #2
Authors: Andrei Romashchenko, Marius Zimand
Accepted on: 29th April 2019 21:02
Keywords:

Abstract:

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, . . . , 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.

Changes to previous version:

Fixed a few minor errors not affecting the main result. Improved presentation

Revision #1 to TR18-043 | 31st August 2018 16:48

#### An operational characterization of mutual information in algorithmic information theory

Revision #1
Authors: Andrei Romashchenko, Marius Zimand
Accepted on: 31st August 2018 16:48
Keywords:

Abstract:

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, . . . , 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.

Changes to previous version:

The presentation is improved. There is no technical change.

### Paper:

TR18-043 | 22nd February 2018 00:46

#### An operational characterization of mutual information in algorithmic information theory

TR18-043
Authors: Andrei Romashchenko, Marius Zimand
Publication: 4th March 2018 22:58
Keywords:

Abstract:

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, . . . , 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.

ISSN 1433-8092 | Imprint