An operational characterization of mutual information in
algorithmic information theory

arXiv:1710.05984v3 [cs.IT] 15 Feb 2018

Andrei Romashchenko

∗

Marius Zimand

†

February 16, 2018

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 ℓ > 2, the longest shared secret that can be established from a tuple of strings (x1 , ..., xℓ )
by ℓ 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.

1

Introduction

Mutual information is a concept of central importance in both information theory (IT) and algorithmic
information theory (AIT), also known as Kolmogorov complexity. We show an interpretation of mutual
information in AIT, which links it to a basic concept from cryptography. Even though a similar interpretation was known in the IT framework, an operational characterization of mutual information in AIT has
been elusive till now.
To present our result, let us consider two strings x and y. It is common to draw a Venn-like diagram
such as the one in Figure 1 to visualize the information relations between them. As explained in the
figure legend there are six important regions. The regions (1) to (5) have a clear operational meaning.
For instance, C(x) is the length of a shortest program that prints x, C(x | y) is the length of a shortest
program that prints x when y is given to it, and so on. On the other hand, the mutual information I(x : y)
from region (6) is defined by a formula: I(x : y) = C(x) + C(y) − C(x, y). Intuitively, it is the information
shared by x and y. But is there an operational interpretation of the mutual information? As mentioned
above, we give a positive answer: The mutual information of x and y is essentially equal to the length of a
longest shared secret key that two parties, one having x and the other one having y, and both parties also
possessing the complexity profile of the two strings, can establish via a probabilistic protocol.
The following simple example illustrates the above concepts. Suppose that Alice and Bob want to agree
on a common secret key. If they could meet face-to-face, they could just generate such a key by, say, flipping
a coin. Unfortunately, they cannot meet in person and what makes the situation really troublesome is that
they can only communicate through a public channel. There is however a gleam of hope because Alice
knows a random line x in the affine plane over the finite field with 2n elements, and Bob knows a random
point y on this line. The line x is specified by the slope a and the intercept b and the point y by its two
∗ Laboratoire d’Informatique,
de Robotique et de
email: andrei.romashchenko@lirmm.fr
† Department
of
Computer
and
Information
http://triton.towson.edu/~mzimand

Microélectronique
Sciences,

1

de

Towson

Montpellier
University,

(LIRMM)

&

CNRS,

Baltimore,

MD.

C(x, y)

C(x)

C(x | y)

C(y)

I(x : y)

C(y | x)

Figure 1: Two strings x and y, and their information. There are six regions that we distinguish: (1) The
left solid circle represents the information in x, as given by its Kolmogorov complexity, denoted C(x); (2)
The right dotted circle represents the information in y, denoted C(y); (3) The entire grey region (the two
circles taken together) represents the information in x and y, denoted C(x, y); (4) The light-grey region
in the first circle represents the information in x conditioned by y, denoted C(x | y); (5) The light-grey
region in the second circle represents the information of y conditioned by x, denoted C(y | x); and (6) the
dark-grey region in the middle represents the mutual information of x and y, denoted I(x : y).
coordinates c and d. Therefore each of x and y has 2n bits of information, but, because of the geometrical
correlation, together they have 3n bits of information. Thus, in principle, Alice and Bob share n bits. Can
they use them to obtain a common secret key? The answer is yes: Alice sends a to Bob, Bob, knowing
that his point is on the line, finds x, and now they can use b as the secret key, because the adversary has
only seen a, and a and b are independent.
It may appear that the geometrical relation between x and y is crucial for the above solution. In fact
it is just a red herring and Alice and Bob can agree on a common secret key in a very general setting. To
describe it, we consider the scenario in which Alice has a random string x and Bob has a random string
y. If x = y, then Alice and Bob can use their common string as a secret key in an encryption scheme
(such as the one-time pad) and achieve perfect information-theoretical security. What happens if x and y
are not equal, but only correlated? Somewhat surprisingly, for many interpretations of “correlated,” they
can still agree on a shared secret key via interaction on a public channel (for instances of this assertion,
see [LYC76, BBR88, Mau93, AC93]). In this paper, we look at this phenomenon using the very general
framework of algorithmic information theory to measure the correlation of strings.
We proceed with a description of our results.

1.1

Our contributions

Characterization of mutual information. In a secret key agreement protocol, Alice and Bob, on input
x and respectively y, exchange messages and compute a common string that is random conditioned by the
transcript of the protocol. Such a string is said to be a shared secret key. Unless specified otherwise, we
use protocols having the following features:
(1) We assume that Alice and Bob also know how their x and y are correlated. In our setting this
means that Alice and Bob know the complexity profile of x and y, which, by definition, is the tuple
(C(x), C(y), C(x, y)).
(2) The protocols are effective and randomized, meaning that Alice and Bob use probabilistic algorithms
to compute their messages.
Theorem 1.1 (Main Result, informal statement)
1. There is a secret key agreement protocol that,
for every n-bit strings x and y, allows Alice and Bob to compute with high probability a shared secret
key of length equal to the mutual information of x and y (up to an O(log n) additive term).
2. No protocol can produce a longer shared secret key (up to an O(log n) additive term).

2

Secret key agreement for three or more parties. Mutual information is only defined for two
strings, but secret key agreement can be explored for the case of more strings. Let us consider again an
example. Suppose that each of Alice, Bob, and Charles have a point in the affine plane over the finite
field with 2n elements, and that the three points, which we call A, B, C, are collinear. Thus each party
has 2n bits of information, but together they have 5n bits of information, because given two points, the
third one can be described with n bits. The parties want to establish a common secret key, but they can
only communicate by broadcasting messages over a public channel. They can proceed as follows. Alice
will broadcast a string pA , Bob a string pB , and Charles a string pC , such that each party using his/her
point and the received information will reconstruct the three collinear points A, B, C. A protocol that
achieves this is called an omniscience protocol because it spreads to everyone the information possessed at
the beginning individually by each party. In the next step, each party will compress the 5n bits, comprising
the three points, to a string that is random given pA , pB , pC . The compressed string is the common secret
key. We will see that up to logarithmic precision it has length 5n − (|pA | + |pB | + |pC |). Assuming we know
how to do the omniscience protocol and the compression step, this protocol produces a common secret
key of length 5n − CO(A, B, C), where CO(A, B, C) is the minimum communication for the omniscience
task for the points A, B, C. In our example, it is clear that each one of pA , pB , pC must be at least n
bits long, and that any two of these strings must contain together at least 3n bits. Using some recent
results from the reference [Zim17], it can be shown that any numbers satisfying these constraints can be
used for the omniscience task. It follows that the smallest communication for omniscience is achieved
when |pA | = |pB | = |pC | = 1.5n, and thus the key has 5n − 4.5n = 0.5n bits (Warning: we have ignored
in the entire discussion some O(log n) terms). We show that this holds in general. If ℓ parties have,
respectively, one component of a tuple (x1 , . . . , xℓ ) of n-bit strings, then up to O(log n) precision, they
can produce a common secret key of length C(x1 , . . . , xℓ ) − CO(x1 , . . . , xℓ ), where CO(x1 , . . . , xℓ ) is the
minimum communication for the omniscience task. The protocol that produces such a key is probabilistic,
and, as was the case for two strings, assumes that each party i has at the beginning of the protocol besides
its input string xi also the complexity profile of the entire tuple (x1 , . . . , xℓ ). We also show a matching (up
to O(log n)) upper bound, which holds for any number of rounds in the protocol.
Communication complexity for secret key agreement. In the protocol in Theorem 1.1, Alice and
Bob exchange min(C(x | y), C(y | x)) + O(log n) bits and obtain with high probability a shared secret key
of length I(x : y) − O(log n). In this protocol we can assume that Alice and Bob use either private random
bits, or public random bits. We show that for the model with public random bits, the communication
complexity of the protocol is optimal, in the sense that in any protocol with public random bits there are
input strings x and y, on which Alice and Bob have to exchange at least min(C(x | y), C(y | x)) bits.
In fact our lower bound is stronger: we show that, for any constants δ1 , δ2 > 0, if Alice and Bob use a
protocol with communication complexity (1 − δ1 ) min(C(x | y), C(y | x)) for every input pair x, y, then
there are inputs for which the shared secret key that they obtain has length at most δ2 I(x : y). That is,
if the communication complexity sinks below the threshold min(C(x | y), C(y | x)), then the size of the
common secret key drops to virtually zero. To determine the optimal communication complexity for the
model with private random bits remains an open problem.

1.2

Related previous work.

IT vs. AIT. Before reviewing existing related results in the IT and the AIT frameworks, it is useful
to understand the distinction between the two theories. In computer science the attribute random is
mainly used in two (fairly different) contexts: random processes and random objects. In short, IT, which
we also call Shannon’s framework, focuses on the former, whereas AIT, which we also call Kolmogorov’s
framework, focuses on the latter. On the one hand, we may think of an uncertain physical process with
unpredictable outcomes, and employ the framework of the classic probability theory (distributions, random
variables, etc.). The notion of a random variable formalizes the idea of a process like coin tossing. In this
context we can measure the uncertainty of a random variable as a whole (by its Shannon’s entropy, its
min-entropy, etc.), but we can not ask whether one specific outcome is random or not. On the other
hand, people use tables of random numbers, which are available as specific sequences of digits, written
on a disc or printed on a paper. The usefulness of such a table depends on its individual properties:
3

frequencies of digits, presence or absence of hidden regularities, compressibility, etc. The usual way to
measure the uncertainty of an individual string of digits is Kolmogorov complexity. In both contexts
the formal measures of randomness may or may not involve computational complexity (see, e.g., different
versions of pseudoentropy for distributions and the resource bounded variants of Kolmogorov complexity
for individual strings). These two formalizations of randomness are connected but not interchangeable.
Both notions of randomness appear in cryptography. For example, in the one-time pad scheme, two
parties share a ‘random’ key that remains ‘secret’ for the attacker. It is common to use Shannon’s framework, and therefore the notions of randomness and secrecy are defined in terms of random processes. In
the ideal situation both parties should have access to a common source of randomness, e.g., to the results
of tossing an unbiased coin (hidden from the adversary). By tossing this coin n times we get a random
variable with maximal possible entropy, and thus, in Shannon’s framework, the quality of randomness is
perfect. But if by chance we obtain a sequence of n zeros, then this specific one-time pad looks pretty
useless in any practical application. However, Shannon’s information theory provides no vocabulary to
complain about this apparently non-random individual key. Antunes et al. [ALPS10] suggested to use
Kolmogorov complexity to measure the ‘secrecy’ of individual instances of a one-time pad or a secret sharing schemes. We have in mind a similar motivation, and in this work a “secret key” is an individual string
that is random in the sense of Kolmogorov complexity.
Related work. We start with a brief account of works on secret key agreement in the IT setting. The
secret key agreement is a relatively well-studied problem in information theory, motivated, as the name
suggests, by applications in information-theoretically secure cryptography. Wyner [Wyn75] and Csiszár
and Körner [CK78] have analyzed the possibility of obtaining a shared secret key in the case when one
party sends to the other party a single message on a channel from which the eavesdropper can obtain
partial information. Maurer [Mau92, Mau93] considered the case of protocols with several rounds of
communication and showed that interaction can be more powerful than one-way transmission. Ahlswede
and Csiszár [AC93] and Maurer [Mau93] have established the tight relation between interactive secret key
agreement and mutual information for memoryless sources. In the memoryless model, the input data is
given by two random variables (X1 , X2 ) obtained by n independent draws from a joint distribution, where
Alice observes X1 and Bob observes X2 . Informally stated, the references [Mau93, AC93] show that the
longest shared secret key that Alice and Bob can establish via an interactive protocol with an arbitrary
number of rounds is equal to the mutual information of X1 and X2 . Csiszár and Narayan [CN04] go beyond
the scenario with two parties, and consider the case of an ℓ-memoryless source (X1 , . . . , Xℓ ) and ℓ parties,
each one observing one component of the tuple. Informally stated, they show that the longest shared secret
key the ℓ parties can establish via an interactive protocol with an arbitrary number of rounds is equal to the
entropy H(X1 , . . . , Xℓ ) of the ℓ-memoryless source from which one subtracts the minimum communication
for omniscience. Their result holds also for stationary ergodic sources, which generalize memoryless sources.
As one can see, our results are very similar. They have been inspired by the papers [AC93, Mau93, CN04]
and represent the AIT analogue of the results presented above. As we explain in Section 7.3, our results
imply their IT analogues, and can be viewed as more general because they do not require the memoryless
or ergodicity properties of sources (in fact they do not require any generative model at all). The question
of finding the communication complexity of secret key agreement protocols in the IT framework has been
raised by Csiszár and Narayan [CN04]. Tyagi [Tya13] has shown that for memoryless sources it is equal
to the difference between interactive common information in Wyner’s sense and mutual information. In
Section 7.3 we explain how Tyagi’s result compares to our results on communication complexity in the AIT
framework.
Let us now say a few words about related results from the AIT world. To the best of our knowledge, in AIT there has been no previous works on secret key agreement. However, the general idea of
“materialization” of mutual information was studied extensively. Motivated by the intuition that mutual
information represents the amount of shared information in two strings, researchers have explored the
extent to which mutual information can be materialized more or less effectively. The relevant concept is
that of common information. Informally, a string z is a common information string extracted from strings
x and y, if z can be “computed” from x, and also from y, where “computed” is taken in a more liberal
sense that allows the utilization of a few help bits. In the most common setting of parameters, we require

4

that C(z | x) = O(log n) and C(z | y) = O(log n), where n is the length of x and y and the constant
hidden in the O(·) notation depends only on the universal machine. Informally, the common information
of x and y is the length of a longest common information string that can be extracted from x and y. It can
be shown that up to logarithmic precision common information is upper bounded by mutual information.
In an influential paper, Gács and Körner [GK73] have constructed strings x and y for which the common
information is much smaller than the mutual information. Moreover, the property of a pair (x, y) of having
common information equal to mutual information does not depend solely on the complexity profile of x and
y: There exist pairs (x1 , y1 ) and (x2 , y2 ) having the same complexity profile, and for (x1 , y1 ) the common
information and mutual information are equal, whereas for (x2 , y2 ) they are not. Muchnik [Muc98] and Romashchenko [Rom00] have strengthened the Gács-Körner theorem in significant ways, by allowing a larger
amount of help bits, parameterizing the mutual information of the constructed pair (x, y), and other ways.
Chernov et al. [CMR+ 02] presents alternative constructions of strings for which the common information
is smaller than mutual information for several regimes of parameters. A nice, self-contained and accessible
exposition of this research line can be found in the book of Shen, Vereshchagin and Uspensky [SUV17,
Chapter 11].
Thus, previous works have shown negative results regarding the “materialization” of mutual information
in AIT. As far as we know, ours is the first positive result. In summary, we now know that computation
without communication, even enhanced with help bits, fails to extract the mutual information of two
strings, while interactive computation succeeds.
Our techniques. It is common for statements in IT (in the Shannon’s entropy framework) to have
an analogue version in AIT (in the Kolmogorov complexity framework). However, there is no canonical
way to translate a result from one setting to the other, and proofs of homologous results in these two
frameworks can be drastically different. A textbook example of this phenomenon is the chain rule: it is
valid for Shannon’s entropy and for Kolmogorov complexity, and the formal expressions of this rule in both
frameworks look very similar. However, in Shannon’s case this fact is an easy corollary of the definition,
while in Kolmogorov’s version it requires a nontrivial argument (which is known as the Kolmogorov–Levin
theorem). There are more advanced examples of parallel properties (from IT and AIT respectively), where
the discrepancy between their proofs is even more striking.
This phenomenon manifests itself in this work as well. Our main results are motivated by similar
ones in IT, and there is a close resemblance of statements. As discussed above, this is not surprising. In
what follows we explain the relation between our proofs and the proofs of similar statements in Shannon’s
framework.
The positive results (the existence of communication protocols) use constructions that at the high
level are akin to those from their IT counterparts [Mau93, AC93, CN04]. We employ a similar intuitive
idea — manipulations with “fingerprints” of appropriate lengths, see Section 3. However, the technical
machinery is different. In the AIT framework, for communication-efficient protocols, we need quite explicit
constructions, while homologous results in IT are usually proven by choosing random encodings. Our
constructions are based on a combination of extractors and universal hashing. Our general protocols are
not time-efficient and this is to be expected given the high generality of the type of data correlation in the
AIT setting. However, for some particular types of correlation (e.g., for a pair of inputs with a bounded
Hamming distance), our protocols can be modified to run in polynomial-time. In this case we use the
reconciliation technique from [Smi07, GS10, GS16].
In the negative results (upper bounds for the size of the common secret key, Theorems 4.1 and 5.5) the
ideas from IT do not help. The reason is that in the AIT framework, the mutual information of various
strings is not exactly zero, but only close to zero within some slack terms. The slack terms are small, but
during the rounds of a protocol, the errors can accumulate and grow beyond control (for more detail see
the discussion of the limits of the “weak” upper bound in Section 3). To overcome this obstacle we come up
with a new type of inequalities for Kolmogorov complexity. These inequalities are substantially different
from the classic information inequalities used in the analogous results in IT. This technique (Lemmas 4.6
and 5.10) is based on ideas similar to the conditional information inequalities in [KR13, KRV15]. We
believe that this technique can be helpful in other cases, including applications in IT (see the discussion in
the full version of the paper).

5

In the proof of a lower bound for communication complexity (Theorem 6.1), we use methods specific for
AIT, with no apparent parallel in IT. We adapt the technique of bounds for the size of common information
that goes back to An. Muchnik and use deep results regarding stochastic strings [She83, MR10, Raz11],
which have not been previously employed in information theory and communication complexity.
Roadmap. In Section 2 we present the necessary basic concepts and results in Kolmogorov complexity
theory used in this paper, and we formally define secret key agreement protocols. Section 3 is a warm-up
section and contains a somewhat simplified version of the main result with a relatively short and selfcontained proof. In Section 4 we prove our main result. Section 5 contains the results on ℓ-parties secret
key agreement protocols, for ℓ ≥ 3. Section 6 presents the results on the communication complexity of
secret key agreement protocols. We conclude with some loose-ends and final comments in Section 7.

2

Preliminaries

2.1

The basics of algorithmic information theory

Algorithmic Information Theory (AIT), initiated independently by Solomonoff [Sol64], Kolmogorov [Kol65],
and Chaitin [Cha66], is a counterpart to the Information Theory (IT), initiated by Shannon. While in IT,
a string is the realization of a random variable, AIT dispenses with the stochastic generative process, and
defines the complexity of an individual string x as the length of its shortest description. For example, the
string x1 = 00000000000000000000000000000000 has low complexity because it can be succinctly described
as “25 zeros.” The string x2 = 10110000010101110101010011011100 is a 32-bit string obtained using random
atmospheric noise (according to random.org), and has high complexity because it does not have a short
description.
Formally, given a Turing machine M , a string p is said to be a program (or a description) of a string x,
if M on input p prints x. We denote the length of a binary string x by |x|. The Kolmogorov complexity of
x relative to the Turing machine M is
CM (x) = min{|p| | p is a program for x relative to M }.
If U is universal Turing machine, then for every other Turing machine M there exists a string m such that
U (m, p) = M (p) for all p, and therefore for every string x,
CU (x) ≤ CM (x) + |m|.
Thus, if we ignore the additive constant |m|, the Kolmogorov complexity of x relative to U is minimal. We
fix a universal Turing machine U , drop the subscript U in CU (·), and denote the complexity of x by C(x).
Below we list below a few basic facts about Kolmogorov complexity and introduce some notation:
1. For every string x, C(x) ≤ |x| + O(1), because a string x is trivially described by itself. (Formally,
there is a Turing machine M that, for every x, on input x prints x.)
2. Similarly to the complexity of x, we define the complexity of x conditioned by y as C(x | y) =
min{|p| | U on input p and y prints x}.
3. Using some standard computable pairing function h·, ·i that maps pairs of strings into single strings,
we define the complexity of a pair of strings by C(x, y) = C(hx, yi). Then we can extend this notation
to tuples of larger arity).
4. We use the convenient shorthand notation a ≤+ b to mean that a ≤ b + O(log n), where n is a
parameter that is clear from the context and the constant hidden in the O(·) notation only depends
on the universal machine U . Similarly, a ≥+ b means a ≥ b − O(log n), and a =+ b means (a ≤+ b
and a ≥+ b).
5. The chain rule in information theory states that H(X, Y ) = H(X) + H(Y | X). A similar rule holds
true in algorithmic information theory: for all sufficiently long strings x and y,
C(x, y) − (C(x) + C(y | x)) ≤ 3(log C(x) + log C(y)).
6

(1)

6. The mutual information of two strings x and y is denoted I(x : y), and is defined as I(x : y) =
C(x) + C(y) − C(x, y). The conditional mutual information is defined in the analogous way: I(x :
y | z) = C(x | z) + C(y | z) − C(x, y | z). It can be shown that mutual information is essentially
non-negative (up to an additive term O(log C(x, y))) and it satisfies the chain rule I(x, z : y) =+
I(z : y) + I(x : y | z) (here the n hidden in the =+ is max(|x|, |y|, |z|)).
7. The complexity profile of a tuple of strings (x1 , . . . , xℓ ) is given by the tuple consisting of the complexities of all non-empty subsets of the strings in the tuple, i.e., it is the tuple (C(xV ) | V ⊆ [ℓ], V 6= ∅).
We use here and elsewhere in the paper the notation [ℓ] for the set {1, . . . , ℓ} and for an ℓ-tuple
(x1 , . . . , xℓ ) and V a subset of [ℓ], xV denotes the subtuple obtained by taking the components with
indices in V (for example if V = {1, 2, 7} then xV = (x1 , x2 , x7 )).
8. The extended complexity profile of a tuple of strings is the tuple of all conditional and unconditional
complexities involving these strings. E.g., the extended complexity profile of a pair (x, y) consists of
the values C(x), C(y), C(x, y), C(x | y), C(y | x).
9. We use the following stronger variant, due to Bruno Bauwens [Bau18] of the main result from reference [Zim17]. It is a version of the Slepian-Wolf theorem about distributed compression of ℓ sources
in the setting of Kolmogorov complexity.
Theorem 2.1 (Distributed compression of ℓ sources) For every constant positive integer ℓ, there
exist a probabilistic encoding algorithms E and a decoding algorithm D such that for every n for every
tuple of n-bit strings (x1 , . . . , xℓ ) and for every tuple of integers (n1 , . . . , nℓ ),
• For every i ∈ [ℓ], E on input xi , ni and ǫ uses O(log(n/ǫ)) random bits and outputs a string pi
of length ni + O(log(n/ǫ)),
P
• For every string y, if the numbers ni satisfy the conditions i∈V ni ≥ C(xV | y, x[ℓ]−V ) for every
V ⊆ [ℓ], then the decoding algorithm D on input y and p1 , . . . , pℓ reconstructs x1 , . . . , xℓ with
probability 1 − ǫ, where the probability is over the randomness used by the encoding procedures.
The following is the particular case of the above theorem for ℓ = 1. A weaker version appeared in
reference [BZ14].
Theorem 2.2 (Single source compression) There exists a probabilistic algorithm that on input
x, k, ǫ, where x is a string, k is a positive integer and ǫ > 0, returns a string p of length k+O(log(n/ǫ)),
and for every y, if k ≥ C(x | y), then with probability (1 − ǫ), p is a program for x given y. The
algorithm is using O(log(n/ǫ)) random bits, where n is the length of x.

2.2

Shared secret keys and protocols for secret key agreement

Let k be a positive integer. A k-rounds two-party protocol for secret key agreement uses two computable
functions A and B and runs as follows. The first party has as input a string xA and uses private randomness
rA , the second party has as input a string xB and uses private randomness rB . We assume that the length
of rA (rB ) is determined by xA (respectively, xB ). The protocol consists of the following calculations:
x1
y1
x2
y2
..
.

= A(xA , rA )
= B(xB , rB , x1 )
= A(xA , rA , y1 )
= B(xB , rB , x1 , x2 )

xk
yk

= A(xA , rA , y1 , . . . , yk−1 )
= B(xB , rB , x1 , . . . , xk ).

The algorithms A and B can handle inputs of different lengths. We also allow them to be partial (i.e., it
is possible that the protocol does not converge for some pairs of inputs). Let ǫ > 0 and δ(n) be a slow
7

growing function (e.g., O(log n) or O(1)). A protocol succeeds with error probability ǫ and randomness
deficiency δ(n) on a pair (xA , xB ) of n-bit strings if with probability (1 − ǫ) over rA , rB ,
def.

A(xA , rA , t) = B(xB , rB , t) = z,

(2)

C(z | t) ≥ |z| − δ(n),

(3)

and
where t = (x1 , y1 , . . . , xk , yk ) is the transcript of the protocol.
The string z satisfying equation (2) and inequality (3) is called a shared secret key output by the
protocol on input (xA , xB ). Note that the shared secret key z is a random variable since it depends not
only on the inputs xA and xB , but also on the randomness rA and rB .
In words, Alice and Bob start with input strings xA and respectively xB , use private randomness rA ,
and respectively rB and execute a protocol in which at round i, first Alice sends to Bob the string xi ,
and next Bob sends to Alice the string yi , and at the end Alice and Bob separately compute with high
probability a common string z (equation (2)) such that z is random even conditioned by transcript of the
protocol (inequality (3)). Thus, z is secret to an adversary that has observed the protocol and consequently
knows the transcript.
Remark 1 In our secret key agreement protocols, the inputs xA and xB have two components: xA =
(x, hA ) and xB = (y, hB ), where the strings x and y are the main components, while hA and hB are
short helping strings (for example, containing information about how x and y are correlated). The communication protocols designed in this paper succeed for all input pairs xA and xB in which hA = hB =
(the complexity profile of x and y). In case one or both of hA and hB are not equal to the complexity
profile, the protocols still halt on every input, but the outputs may be meaningless.

3

Warm-up: Short proofs for “light”-versions of the main results

Our main result has two parts: the lower bound, which consists of a protocol that produces a shared secret
key of length equal (within logarithmic precision) to the mutual information of the inputs, and the upper
bound, where we show that it is impossible to obtain a longer shared secret key. We present here light
versions of these two parts. We call them light because they have weaker parameters than the full-fledged
results, which are presented in Section 4. On the other hand, they admit short and self-contained proofs.
Moreover, since they have a common structure, these proofs are a useful preamble for the proofs in the
next section.
The light lower bound consists of a protocol that does allow two parties, one having the n-bit string
x and the other having the n-bit string y, to obtain a shared secret key of length approximately equal to
I(x : y), but which communication-wise is inefficient. In Section 4 we present an improved protocol that
achieves the same task, with communication complexity equal essentially to min(C(x | y), C(y | x)), which
we conjecture to be optimal (see Section 6). The light upper bound consists of a proof in which we show
that no protocol with a constant number of rounds and poly(n) random bits can produce a secret key
longer than the mutual information. In Section 4, we lift the restrictions regarding the number of rounds
and random bits.
The light lower bound.1 The setting is that Alice has the n-bit string x, and Bob has the n-bit string
y. In addition, both Alice and Bob have the complexity profile of x and y. We construct a protocol that
allows Alice and Bob to agree with probability 1 − ǫ on a shared secret key of length I(x : y) − O(log(n/ǫ)
and randomness deficiency δ(n) = O(log(n/ǫ)). The protocol has 1 round, and actually the communication
consists of a single message from Alice to Bob.
We start with an overview of the proof in a “nutshell.” First, Alice chooses two hash-functions h1 and
h2 from two families of hash functions which are publicly known. Alice sends h1 and h2 to Bob, and she
also sends to Bob the hash value h1 (x). Next, Bob attempts to reconstruct Alice’s input: he searches over
1 The

following proof is due to Bruno Bauwens (private communication, August 2017).

8

all x′ such that C(x′ | y) ≤ C(x | y) until he finds a candidate with the same hash value, h1 (x′ ) = h1 (x);
in what follows he hopes that the x′ he found is indeed Alice’s string x. Next, Alice and Bob compute the
value h2 (x) and take it as the common secret key.
In this scheme the adversary gets to know the hash functions h1 , h2 and the hash-value h1 (x). For
this to work, we want to guarantee that with high probability Bob finds the correct value of x (absence of
collisions) and that the adversary gets very little information regarding the secret h2 (x). The technical part
of the proof consists in choosing appropriate families of hash functions, which guarantee the two required
properties.
In this section we use a very simple hashing technique — we take h1 and h2 to be random linear
mappings with suitable lengths of the output. In the next section we use Theorem 2.2, which provides a
subtler implementation of the same idea, where the ‘hashing’ is based on extractors.
In what follows we present in more detail the easy version of the protocol, with linear hashing.
Step 1: Let n1 = C(x) and let k = C(x | y). (In fact, Alice does not have k. But she can compute from
the complexity profile x and y, a good approximation of k; this is a small nuisance which can be easily
handled, and for the sake of simplicity we ignore it.) Alice chooses an n1 + log(1/ǫ)-by-n random binary
matrix H. Alice partitions H into two sub-matrices H1 and H2 , where H1 consists of the top k + log(1/ǫ)
rows of H, and H2 consists of the bottom n1 − k rows of H. Alice calculates q = H1 x, and sends q and
the entire H to Bob. Let E1 be the event that there exists x′ 6= x such that C(x′ ) ≤ C(x) and Hx′ = Hx
and E2 be the event that there exists x′′ 6= x such that C(x′′ | y) ≤ C(x | y) and H1 x′′ = H1 x. Note that
both E1 and E2 have probability at most ǫ. Consequently with probability at least 1 − 2ǫ, neither E1 nor
E2 hold, an event that we assume henceforth. We also assume
C(x, y | H) ≥ C(x, y) − O(log(1/ǫ)),

(4)

an event which holds with probability at least 1 − ǫ.
Step 2: Since x is the unique string such H1 x = q among strings that have complexity conditioned by y
bounded by k, Bob reconstructs x from q and H. Next, both Alice and Bob compute the string z = H2 x,
which is the output of the protocol.
Let us now show that z has the desired properties. Note first that z has length n1 − k = C(x) − C(x |
y) =+ I(x : y). It remains to show that z is a shared secret key, i.e., that z is random conditioned by the
transcript of the protocol, which consists of q and H. More precisely, we show that C(z | q, H) ≥ I(x :
y) − O(log(n/ǫ). Since x can be computed from q, z and H,
C(x, y | H) ≤ C(q, z, y | H) + O(1).

(5)

= C(q | H) + C(z | q, H) + C(y | q, z, H) + O(log n)
≤ C(x | y) + C(z | q, H) + C(y | x) + O(log(n/ǫ)).

(6)

Next, by the chain rule,
C(q, z, y | H)

In the second line, we have taken into account that C(q | H) is less than |q| + O(1) = C(x | y) + log(1/ǫ) +
O(1), and C(y | q, z, H) is less than C(y | x) + O(1) (because x can be computed from q, z, H). Combining
equations (5) and (6), we obtain
C(z | q, H) ≥ C(x, y | H) − C(x | y) − C(y | x) − O(log(n/ǫ))
≥ C(x, y) − C(x | y) − C(y | x) − O(log(n/ǫ)) (using equation (4))
≥ I(x : y) − O(log(n/ǫ)).

Remark 2 The defined protocol has communication complexity O(n2 ) (mostly due to the necessity to
communicate the matrix H). The communication complexity of the protocol can be easily reduced to O(n)
if we take at random not an arbitrary matrix H but a random Toeplitz matrix of the same size. In the
next section we describe a protocol with communication complexity min(C(x | y), C(y | x)). (We show in
Section 6 that no protocol with public randomness has smaller communication complexity, and we conjecture
that the same holds for protocols with private randomness.)
9

The light upper bound. We show here that if k is a constant and the number of random bits is
bounded by a polynomial in n, no k-round protocol can produce a shared secret key that is longer (up to
logarithmic precision) than the mutual information of the inputs. More precisely, our claim is that if a
shared secret key z is produced from inputs xA , xB by some k-round protocol with probability 1 − ǫ, then
C(z | t) ≤ I(xA : xB ) + O(k log(n/ǫ)) with probability 1 − O(ǫ), where t is the transcript of the protocol.
Simple warm-up: deterministic protocols without communication. Let us first consider the case k = 0,
i.e., Alice and Bob do not interact, and also, for now, let us assume they use no randomness. Clearly, this
model is very weak, and in general Alice and Bob cannot agree on any nontrivial common secret without
communication. However, in some cases (for some very special inputs xA and xB ) this might be possible.
For instance, if xA and xB are n-bits strings of complexity n, and the first n/2 bits in these strings coincide
(the i-th bit of xA is equal to the i-th bit of xB for i = 1, . . . , n/2), then Alice and Bob can take the first
n/2 bits of their inputs as the common key.
In this trivial example Alice and Bob get a common key of complexity close to n/2, and the mutual
information between xA and xB is also not less than n/2. We argue that the same relation remains true
for all protocols without communication, for all pairs of inputs (xA , xB ). That is, if Alice and Bob can
extract from their inputs xA and xB the same string z without communication, then the complexity of this
z is bounded by I(xA : xB ). This follows from a well-known inequality that is true for all xA , xB , z:
C(z) ≤+ C(z | xA ) + C(z | xB ) + I(xA : xB ).

(7)

Slightly more freedom: randomized protocols without communication. The same bound remains true if
Alice and Bob use random strings rA and rB (still without communication). Indeed, using Lemma A.7 (3),
with probability 1 − O(ǫ), we have
I(xA , rA : xB , rB ) = I(xA : xB ) ± O(log(n/ǫ)).

(8)

Hence, we can apply the same argument to the pair (hxA , rA i, hxB , rB i).
C(z) ≤+ C(z | xA , rA ) + C(z | xB , rB ) + I(xA , rA : xB , rB )
=+ C(z | xA , rA ) + C(z | xB , rB ) + I(xA : xB ) ± O(log(n/ǫ))

(9)

(the first inequality in (9) is always true, while the last equality is true with probability 1 − O(ǫ).) In case
when z is a computable function of (xA , rA ) and a computable function of (xB , rB ), we obtain from (9)
that with probability 1 − O(ǫ)
C(z) ≤ I(xA : xB ) + O(log(n/ǫ)),
(10)
and we are done.
The general case: randomized protocols with O(1)-round communication. Let us move now to the case
when the number of communication rounds is k > 0. As announced, we claim that the upper bound
remains true: C(z | t) ≤ I(xA : xB ) + O(k log(n/ǫ)). The proof for the “light” case in which k is constant
proceeds as follows.
Inequality (7) has a relativized version,
C(z | t) ≤+ C(z | xA , rA , t) + C(z | xB , rB , t) + I(xA , rA : xB , rB | t),

(11)

which is true for all xA , xB , rA , rB , z, t. When z is a computable function of (xA , rA , t) and a computable
function of (xB , rB , t), we obtain
C(z | t) ≤+ I(xA , rA : xB , rB | t).

(12)

Thus, to prove our claim, it remains to show that for the transcript t
I(xA , rA : xB , rB | t) ≤+ I(xA , rA : xB , rB ).

(13)

and then to use inequality (8).
Notice that in general the conditional mutual information I(a : b | c) can be much larger than the plain
mutual information I(a : b) (e.g., if a and b are independent strings of length n and c is the bitwise XOR
of a and c, then I(a : b | c) =+ n ≫ I(a : b) =+ 0). So, we should explain why (13) is true for these specific
strings. The required inequality can be deduced from the following lemma.
10

Lemma 3.1 (a) Let f be a computable function of one argument. Then for all a, b
I(a : b | f (a)) ≤+ I(a : b).

(14)

(b) Further, let g be a computable function of two arguments. Then for all a, b, c
I(a : b | f (a, c), c) ≤+ I(a : b | c).

(15)

Proof Inequality (14) follows directly from the chain rule:
I(a : b) =+
=+
≥+

I(a, f (a) : b)
I(f (a) : b) + I(a : b | f (a))
I(a : b | f (a))

(since f (a) can be computed from a)
(the chain rule)
(non-negativity of the mutual information)

The proof of (15) is similar, we should only substitute c as a condition to each term I(∗) in the inference
above. The lemma is proven.
Now we proceed with a proof of (13). Recall from the definition of a protocol, that t = (x1 , y1 , . . . , xk , yk )
and each xi (respectively yi ) is deterministically computed from xA , rA (respectively from xB , rB ) and the
previous messages. We claim that
I(xA , rA : xB , rB ) ≥+ I(xA , rA : xB , rB | x1 )
≥+ I(xA , rA : xB , rB | x1 , y1 )
≥+ I(xA , rA : xB , rB | x1 , y1 , x2 )
..
.

(16)

≥+ I(xA , rA : xB , rB | x1 , y1 , x2 , y2 , . . . , xk , yk ).
The first line is a special case of (14) since x1 can be computed from (xA , rA ). Every next line is a special
case of (15). Indeed, on each step we add to the condition of the term I(xA , rA : xB , rB | ∗) another
string xi or yi , and every time the newly added string is a function of (xA , rA ) and the pre-history of the
communication or of (xB , rB ) and the pre-history.
All the inequalities used in the argument are valid up to an additive term O(log C(xA , rA , xB , rB )),
which is at most O(log n) because rA and rB have length bounded by a polynomial in n. Since the number
of rounds k (and therefore the chain of inequalities (16)) is constant, the claimed upper bound is proved.
To prove the same inequality for a non-constant k and an arbitrary number of random bits we will need
a different technique. We discuss it in Section 4.

4

Main results

We prove here our main results. We present a secret key agreement protocol which produces a shared
secret key of length equal (up to logarithmic precision) to the mutual information of the inputs, provided
the two parties know the complexity profile. Next we show that no protocol can produce a longer shared
secret key. The formal statements are as follows.
Theorem 4.1 (Lower bound) There exists a secret key agreement protocol with the following property:
For every n-bit strings x and y, for every constant ǫ > 0, if Alice’s input xA consists of x, the complexity
profile of (x, y) and ǫ, and Bob’s input xB consists of y, the complexity profile of (x, y) and ǫ, then,
with probability 1 − ǫ, the shared secret key is a string z such that, C(z | t) ≥ |z| − O(log(1/ǫ)) and
|z| ≥ I(x : y) − O(log(n/ǫ)), where t is the transcript of the protocol.
Moreover, the communication consists of a single message sent by Alice to Bob of length C(x | y) +
O(log(n/ǫ)), Alice uses O(log(n/ǫ)) random bits, and Bob does not use any random bits.
Theorem 4.2 (Upper bound) Let us consider a protocol for secret key agreement, let xA and xB be
input strings of length n on which the protocol succeeds with error probability ǫ and randomness deficiency
δ(n), and let z be the random string that is the shared secret key output by the protocol, i.e., a string
satisfying relations (2) and (3). Then with probability at least 1 − O(ǫ),
if n is sufficiently large, |z| ≤ I(xA : xB ) + δ(n) + O(log(n/ǫ)), where the constants in the O(·) notation
depend on the universal machine, but not on xA and xB .
11

Theorem 4.2 establishes the upper bound claimed in the Introduction. Indeed, for any pair of n-bit
strings (x, y), suppose that Alice’s input xA consists of x and the complexity profile of (x, y) and Bob’s
input xB consists of y and the complexity profile of (x, y). Note that I(xA : xB ) =+ I(x : y), because
the length of the complexity profile is bounded by O(log n). Hence, Theorem 4.2 implies that secret key
agreement protocols in which the two parties, besides x and respectively y, are additionally given the
complexity profile of their inputs can not produce a secret key that is longer than I(x : y) + O(log n)
(provided the randomness deficiency of the key satisfies δ(n) = O(log n)).
Proof of Theorem 4.1. We first give an overview of the protocol (an adaptation of the scheme “in
a nutshell” explained on p. 8).
In Step 1, Alice computes px|y a program for x given y of length C(x | y) + O(log n). She sends to Bob
the string px|y and also random strings r and s that both Alice and Bob will use in Step 2. The strings r
and s have length O(log(n/ǫ)).
In Step 2, Bob uses px|y and his string y, to construct x. Next, both Alice and Bob construct a
O(log n)-short program for x given px|y using the random string r. This is the common output z of the
protocol.
Let us now see the details.
Step 1. Alice, using the complexity profile of x and y, first computes k = C(x, y) − C(x) + 4 log n.
Taking into account relation (1), if n is sufficiently large, C(x | y) + 8 log n ≥ k ≥ C(x | y). Next, using the
algorithm from Theorem 2.2, Alice on input (x, k, ǫ) computes a string px|y that, with probability 1 − ǫ, is
a program for x given y of length k + O(log(n/ǫ)) ≤ C(x | y) + O(log(n/ǫ)). In what follows, we assume
that px|y has this property (thus, we exclude an event that has probability at most ǫ).
Note that C(px|y ) ≥ C(x | y) (because px|y is a program for x given y), and C(px|y ) ≤ |px|y | + O(1) ≤
k + O(log(n/ǫ)) ≤ C(x | y) + O(log(n/ǫ)). Thus, C(px|y ) =+ C(x | y).
Next,
C(x | px|y )

=+ C(x, px|y ) − C(px|y ) (chain rule)
=+ C(x) − C(x | y) (px|y is computed from x and O(log(n/ǫ)) randomness)
=+ I(x : y).

(17)

Alice sends to Bob the string px|y and also random strings r and s of length O(log(n/ǫ)) that will be
used by both parties in Step 2.
Step 2. First, Bob reconstructs x from y and px|y .
Next, both Alice and, separately, Bob do the following. In the first phase, they use the random string r
(from Step 1) and compute a string z̃, which almost has the desired properties, except that its randomness
deficiency is a little too large. In a second phase, they use the random string s (also from Step 1), to finally
obtain z with all the desired properties.
Phase 1. Using the complexity profile of x and y and based on relation (17), Alice and Bob compute
k ′ = I(x : y) + c′ log(n/ǫ), for a constant c′ such that C(x|px|y ) ≤ k ′ . Then, using the algorithm from
Theorem 2.2 on input (x, k ′ , ǫ), with randomness given by the random string r from Step 1, they compute
a string z̃ of length k ′ + O(log(n/ǫ)). With probability (over r) at least 1 − O(ǫ), z̃ is a program for x
given px|y . In what follows, we assume that z̃ has this property (thus, we exclude another event that has
probability at most O(ǫ)).
Note that |z̃| = k ′ + O(log n) =+ I(x : y) and C(z̃) ≤ |z̃| + O(1) ≤+ I(x : y). Also
C(z̃ | px|y ) ≥+ C(x | px|y )
=+ I(x : y).

(because z̃ is a program for x given px|y )
(by using inequality (17))

Combining the last three relations, it follows that
|z̃| =+ C(z̃) =+ C(z̃ | px|y ) =+ I(x : y),
The transcript of the protocol (without s which has not been used yet) is t = (px|y , r), and since |r| =
O(log(n/ǫ)), we get
C(z̃ | t) ≥ I(x : y) − O(log(n/ǫ)) and |z̃| ≥ I(x : y) − O(log(n/ǫ)).
12

(18)

Thus, we are almost done, except for the fact that the randomness deficiency of z̃ is O(log(n/ǫ)), which is
too large.
Phase 2. To reduce the randomness deficiency, we need to use a strong extractor. Recall that a function
E : {0, 1}n × {0, 1}d → {0, 1}m is a (k, ǫ) extractor if for any set B ⊆ {0, 1}n of size |B| ≥ 2k , and for any
A ⊆ {0, 1}m,

|A|
|A|
− ǫ,
+ǫ ,
Prob(E(UB , U{0,1}d ) ∈ A) ∈
M
M
where UB , U{0,1}d denote independent random variables uniformly distributed on B, and respectively
{0, 1}d, and M = 2m .
A function E : {0, 1}n × {0, 1}d → {0, 1}m is a (k, ǫ) strong extractor if the function E1 defined by
E1 (x, y) = (y, E(x, y)) is a (k, ǫ) extractor. Using the probabilistic method, one can show that there exist
strong extractors with m = k − 2 log(1/ǫ) − O(1) and d = log n + 2 log(1/ǫ) + O(1) [Vad12, Theorem 6.17].
Alice and Bob compute by brute-force such a strong extractor E.
For some value of k = I(x : y) − O(log(n/ǫ)) (the exact value of k is specified in the proof of the next
lemma), Alice and Bob use the strong (k, ǫ) extractor E : {0, 1}|z̃| × {0, 1}d → {0, 1}m (with d and m as
above), and the random string s from Step 1, and take z = E(z̃, s). Intuitively, by the properties of a
strong extractor, the output z is random even conditioned by the seed s, which is exactly what we need
here. The following lemma, whose proof is given in Appendix A.1, shows that indeed z has the desired
properties.
Lemma 4.3 Let E be the above strong extractor, and suppose z̃ satisfies inequalities (18). If s is chosen
uniformly at random in {0, 1}d, and z = E(z̃, s), then with probability 1−O(ǫ), C(z | t, s) ≥ |z|−O(log(1/ǫ))
and |z| = I(x : y) − O(log(n/ǫ)).
This concludes the proof of the theorem.
Remark 3 The proof of Theorem 4.1 can be adapted to the situation where Alice and Bob are not given
the exact value of the complexity profile of (x, y) but only an approximation of this profile. Indeed, assume
that Alice and Bob are given upper and lower bounds for each component of the complexity profile of (x, y)
with precision ≤ σ, for some integer σ. Then we can use the communication protocol from the proof of
Theorem 4.1 where the length of px|y is chosen in accordance with the upper bound on C(x | y), and the
length of the resulting key z is chosen in accordance with the lower bound on the value of I(x : y). As
a result, with probability 1 − O(ǫ) Alice and Bob agree on a common secret z that is incompressible (i.e.,
C(z | t) ≥ |z| − O(log(1/ǫ)) where t is the transcript of the protocol ), and the length of z is greater than
I(x : y) − σ − O(log(n/ǫ)).
Proof of Theorem 4.2 Similarly to the argument in the light upper bound of the previous section, we
are going to combine inequalities (12) and (13). All we need to do is to establish inequality (13) for the
case when the number of rounds k is non-constant. The challenge is that we cannot iterate k applications
of Lemma 3.1. If k is not a constant, then the sum of k copies of O(log n) terms in (16) becomes too large.
Thus, we need to handle the transcript t “in one piece,” without splitting it in k messages. To this end we
have to use instead of Lemma 3.1 some other tool.
We start with a reminder of the notion of a combinatorial rectangle (pretty standard in communication
complexity).
Definition 4.4 A set S ⊂ {0, 1}∗ × {0, 1}∗ is a combinatorial rectangle, if it can be represented as a
Cartesian product S = A × B for some A, B ⊂ {0, 1}∗ .
For example, in Fig. 2 the black cells in the table form a combinatorial rectangle (the black cells occupy the
intersection of columns a1 , a2 , a3 , a4 and rows b1 , b2 , b3 ). We use the notion of a combinatorial rectangle in
the following (less conventional) definition.
Definition 4.5 We say that a computable function f : {0, 1}∗ × {0, 1}∗ → {0, 1}∗ is transcript-like, if for
every t, the pre-image f −1 (t) is a combinatorial rectangle.

13

b3
b2
b1
a1

a2

a3

a4

Figure 2: Combinatorial rectangles.

For examples, the cells in the table in Fig. 2 are colored in four different colors (solid black, solid grey,
and two types of hatching), and cells of each color form a combinatorial rectangle. Thus, the function that
maps each cell to its color is transcript-like.
By definition, for every transcript-like function f , if f (a, b′ ) = f (a′ , b) = t for some a, a′ , b, b′ , then we
have also f (a, b) = t. Notice that for every deterministic communication protocol with two parties (Alice
and Bob) the mapping
f : [input of Alice xA ] × [input of Bob xB ] 7→ [the transcript of the protocol]
is transcript-like. A similar statement holds for randomized protocols with private source of randomness,
we should only join the random bits given to Alice and Bob with their inputs : the mapping
f : hxA , rA i × hxB , rB i 7→ [the transcript of the protocol]
is also transcript-like.
Now we formulate a generalization of Lemma 3.1 (a), which can work with the transcript of the protocol
‘in one piece’.
Lemma 4.6 If f : {0, 1}∗ × {0, 1}∗ → {0, 1}∗ is transcript-like function, then for all a, b
I(a : b | f (a, b)) ≤+ I(a : b).

(19)

Remark 4 If f depends only on a or only on b, then f is transcript-like. Thus, Lemma 3.1 (a) is a special
case of Lemma 4.6.
Proof Let us fix a pair (a, b) and denote t := f (a, b). We say that a string a′ is an A-clone of a (conditional
on t), if
(iA ) there exists another string b′ such that f (a′ , b′ ) = t, and
(iiA ) each coordinate of the extended complexity profile of (a′ , t) is not greater than the corresponding
coordinate of the extended complexity profile of (a, t). That is, the quantities C(a′ ), C(a′ , t), C(a′ | t),
and C(t | a′ ) are not greater than C(a), C(a, t), C(a | t), and C(t | a) respectively.
Similarly, we say that b′ is a B-clone of b (conditional on t), if
(iB ) there exists another tuple a′ such that f (a′ , b′ ) = t, and
(iiB ) each coordinate of the extended complexity profile of (b′ , t) is not greater than the corresponding
coordinate of the extended complexity profile of (b, t).

14

Notice that given t and the extended complexity profiles of (a, t) and (b, t), we can run the process of enumeration of all A- and B-clones. Thus, to identify some specific clone given t we need to know the extended
complexity profiles of (xA , t) and (xB , t) respectively (which takes only O(log n) bits of information) and
the index of that clone in the list of enumeration.
Denote the sets of A-clones and B-clones by ClonesA and ClonesB respectively. By definition we have
a ∈ ClonesA and b ∈ ClonesB . Let us show that in fact there exist many other A- and B-clones.
Claim 4.7 2C(a|f (a,b))−O(log n) ≤ |ClonesA | ≤ 2C(a|f (a,b))+1 and 2C(b|f (a,b))−O(log n) ≤ |ClonesB | ≤ 2C(b|f (a,b))+1 .
Proof of the claim: Indeed, these sets cannot be bigger than that (since by definition for all clones we have
C(a′ | t) ≤ C(a | t) and C(b′ | t) ≤ C(b | t)) and also cannot be smaller (otherwise, as explained above,
given t we could specify a and b by their indices in the enumerable lists of all clones, and C(a | t) and
C(b | t) would be too small).
Let us take a pair of “typical” clones (a′ , b′ ) ∈ ClonesA × ClonesB that maximizes C(a′ , b′ | t). Due to
the claim above, this maximum is
C(a′ , b′ | t) ≥+
=+

log |ClonesA × ClonesB |
C(a | t) + C(b | t).

Thus, we have
C(a′ , b′ , t) =+ C(t) + C(a′ , b′ | t) ≥+ C(t) + C(a | t) + C(b | t).

(20)

By definition of clones, a′ and b′ belong to the projection of the pre-image f −1 (t). Since f is a transcriptlike function, it follows that f (a′ , b′ ) = t. That is, given a′ and b′ we can compute t, so C(t | a′ , b′ ) =+ 0.
Hence, the left hand side of (20) can be upper bounded as
C(a′ , b′ , t) ≤+ C(a′ ) + C(b′ ) ≤+ C(a) + C(b)

(21)

(in the last inequality we used again the definition of clones). Combining (20) and (21) we obtain
C(t) + C(a | t) + C(b | t) ≤+ C(a) + C(b).

(22)

Given C(t | a, b) =+ 0, inequality (22) rewrites to I(a : b | t) ≤+ I(a : b), and lemma is proven.
Now we are ready to prove the theorem. Denote by π the function
′
′
π : hx′A , rA
i × hx′B , rB
i 7→ [the transcript of the protocol]

mapping the input data of Alice and Bob to the corresponding transcript of the communication protocol.
Clearly, π is a transcript-like function (as the outcome of any communication protocol). By applying
Lemma 4.6 to the function π we get inequality (13). This concludes to proof of the theorem.
Remark 5 The proof of inequality (13) applies even to “invalid” input data xA and xB , when Alice and
Bob are given false information on the complexity profile of the main input components x and y. (See
Remark 1).
Remark 6 In some sense the proof of the weaker ‘light upper bound’ in section Section 3 is more robust
than the proof of Theorem 4.2, since it applies to protocols with small advice obtained from a trustable
all-powerful helper, see Appendix A.4.

5

Secret key agreement for 3 or more parties

We analyze secret key agreement for 3 or more parties. All the results in this section are valid for any
constant number ℓ ≥ 3 of parties. For notational convenience, we handle the case of ℓ = 3 parties, but the
proofs with straightforward adaptations are valid for any constant ℓ.

15

Thus this time there are three parties, which we call Alice, Bob, and Charles. Alice has a string xA ,
Bob has a string xB , and Charles has a string xC . They also have private random bits rA , respectively
rB and rC . They run a k-round protocol. In each of the k rounds, each party broadcasts a message to
the other two parties, where the message is a string computed from the party’s input string and private
random bits, and the messages from the previous rounds. After the completion of the k rounds, each party
computes a string. The requirement is that with probability at least 1 − ǫ, they compute the same string,
and that this string is random conditioned by the transcript of the protocol.
Formally, a k-round 3-party protocol for secret key agreement uses three computable functions A, B, C,
and runs as follows. The first party has as input an n-bit string xA and uses private randomness rA ,
the second party has as input an n-bit string xB and uses private randomness rB , and the third party
has as input an n-bit string xC and uses private randomness rC . The protocol consists of the following
calculations:
t1 = A(xA , rA ),
t4 = A(xA , rA , t[1 : 3]),
..
.

t2 = B(xB , rB ),
t5 = B(xB , rB , t[1 : 3]),

t3 = C(xC , rC ),
t6 = C(xC , rC , t[1 : 3]),

t3k−2 = A(xA , rA , t[1 : 3(k − 1)]), t3k−1 = B(xB , rB , t[1 : 3(k − 1)]), t3k = C(xC , rC , t[1 : 3(k − 1)])
Each row corresponds to one round and shows the messages that are broadcast in that round, and we use
the notation t[i : j] to denote the tuple of messages (ti , . . . , tj ). We also denote t = t[1 : 3k], the entire
transcript of the protocol. The protocol succeeds with probability error ǫ and randomness deficiency δ(n)
on the 3-tuple input (xA , xB , xC ) if with probability (1 − ǫ) over rA , rB , rC ,
def.

A(xA , rA , t) = B(xB , rB , t) = C(xC , rC , t) = z,

(23)

C(z | t) ≥ |z| − δ(n).

(24)

and

5.1

Omniscience: definitions and explicit expressions

We transfer to AIT the notion of omniscience introduced in IT:
Definition 5.1 (1) For each triple of strings (xA , xB , xC ), we denote by S(xA , xB , xC ) the set of all
triples of integers (nA , nB , nC ) that satisfy the following inequalities:
nA ≥ C(xA | xB , xC ),
nB ≥ C(xB | xA , xC ),
nC ≥ C(xC | xA , xB ),
nA + nB ≥ C(xA , xB | xC ), nA + nC ≥ C(xA , xC | xB ), nB + nC ≥ C(xB , xC | xA ).

(25)

The constraints defining S(xA , xB , xC ) will be referred as the Slepian-Wolf constraints.
(2) We define CO(xA , xB , xC ) to be the minimal value of nA + nB + nC subject to nA , nB , nC satisfying
the Slepian-Wolf constraints. (CO stands for communication for omniscience.)
This definition has a straightforward (though rather cumbersome) generalization for the tuples of size ℓ > 3:
Definition 5.2 (1) For each triple of strings (x1 , x2 , . . . , xℓ ), we denote by S(x1 , x2 , . . . , xℓ ) the set of
all triples of integers (n1 , n2 , . . . , nℓ ) that satisfy the following inequalities: for every splitting of the
set of all indices into two disjoint nonempty sets, {1, . . . , ℓ} = I ∪ J , we have
P
ni ≥ C(xI | xJ ).
(26)
i∈I

Similar to the case of ℓ = 3, the constraints defining S(x1 , x2 , . . . , xℓ ) are referred as the Slepian-Wolf
constraints.
(2) We define CO(x1 , x2 , . . . , xℓ ) to be the minimal value of n1 + · · · + nℓ subject to n1 , . . . , nℓ satisfying
the Slepian-Wolf constraints.
16

The value of CO(xA , xB , xC ) can be viewed as the solution of a problem of linear programming defined by
constraints (25). This solution can be computed explicitly, as shown in the following proposition.
Proposition 5.3 (see Example 3 in [CN04]) The value of CO(xA , xB , xC ) is equal to the maximum
of the following four quantities
C(xA | xB , xC ) + C(xB , xC | xA ),
C(xB | xA , xC ) + C(xA , xC | xB ),
C(xC | xA , xB ) + C(xA , xB | xC ),
1
2 [C(xA , xB | xC ) + C(xA , xC | xB ) + C(xB , xC | xA )] .
Accordingly, the difference C(xA , xB , xC ) − CO(xA , xB , xC ) is equal to the minimum of the following four
quantities:
I(xA : xB , xC ),
I(xB : xA , xC ),
(27)
I(xC : xA , xB ),
1
2 [C(xA ) + C(xB ) + C(xC ) − C(xA , xB , xC )] .
This result can be extended to the case ℓ > 3 as follows.
Proposition 5.4 ([CABE+ 15]) For every tuples of strings (x1 , . . . , xℓ ) the difference C(xA , xB , xC ) −
CO(xA , xB , xC ) is equal to the minimum of the quantities
1
s−1

[C(xJ1 ) + . . . + C(xJs ) − C(x1 , . . . , xℓ )] .

(28)

over all splittings {1, . . . , ℓ} = J1 ∪ J2 ∪ . . . ∪ Js , where J1 , . . . , Js are nonempty and disjoint.
Remark 7 It is easy to see that the minimum of four values (27) is a special case of the minimum of (28)
(for ℓ = 3).
In what follows we show that there exists a protocol that on every input tuple (xA , xB , xC ) produces
with high probability a secret key of length C(xA , xB , xC ) − CO(xA , xB , xC ) − O(log n) (provided the
parties have the complexity profile of the input tuple), and that no protocol can produce a secret key of
length larger than C(xA , xB , xC ) − CO(xA , xB , xC ) + O(log n). We prove the upper bound in Section 5.2
we the lower bound and in Section 5.3.

5.2

Negative result for multi-party protocols

In this section we prove the upper bound on the length of the longest secret key that Alice, Bob, and Charles
can agree upon. A weak version of this bound (for the protocols with O(1) rounds) can be obtained with
the technique of classic information inequalities, very similar to the proof of an analogous statement in
[CN04] in the setting of IT. We only need to “translate” the information inequalities for Shannon’s entropy
from the proof in [CN04] in homologous inequalities for Kolmogorov complexity, see Appendix B. However,
this technique does not work for protocols with non constant number of rounds. So to prove our next
theorem we use a pretty different method, employing the method of “clones” and constraint (non classic)
information inequalities. This argument generalizes the proof of Theorem 4.2.
Theorem 5.5 Let us consider a 3-party protocol for secret key agreement with error probability ǫ. Let
(xA , xB , xC ) be a 3-tuple of n-bit strings on which the protocol succeeds. Let z be the random variable
which represents the secret key computed from the input (xA , xB , xC ) and let t be the transcript of the
protocol that produces z. Then, for sufficiently large n, with probability 1 − O(ǫ),
C(z | t) ≤ C(xA , xB , xC ) − CO(xA , xB , xC ) + O(log

n
),
ǫ

where the constants in the O(·) notation depend on the universal machine, but not on (xA , xB , xC ).

17

Proof Assume that Alice, Bob, and Charlie agreed on a common key z. Denote by t the transcript
of the communication protocol. We need to show that C(z | t) is not greater than the minimum of four
quantities (27).
Trivial case: no communication nor randomness. Similarly to the light upper bound in Section 3, we
start with a naive question: on which z Alice, Bob, and Charlie can agree without any communication?
The upper bound from Section 3 applies to the case of three participants. Indeed, inequality (7) specializes
to
C(z) ≤+ C(z | xA , xB ) + C(z | xC ) + I(xA , xB : xC ).
Hence, if z can be computed by Alice, Bob, and Charlie given each of the strings xA , xB , xC , then
C(z) ≤+ I(xA , xB : xC ).

(29)

C(z) ≤+ I(xA , xC : xB )

(30)

C(z) ≤+ I(xB , xC : xA ).

(31)

Similarly, we have
and
In addition to the three mutual information quantities handled above, the maximum in (27) involves
another quantity, which is specific for protocols with three participants. We treat it separately:
Lemma 5.6 If z can be computed from each of the strings xA , xB , xC , then
C(z) ≤+

1
(C(xA ) + C(xB ) + C(xC ) − C(xA , xB , xC )) .
2

(32)

(See the proof in Appendix.)
The combination of (29), (30), (31), (32) implies that if a string z can be “extracted” from xA , xB ,
and xC (without communication), then its complexity C(z) is not greater than (27).
Randomized protocol without communication. We join xA , xB , and xC with strings of random bits rA ,
rB , rC , and repeat the same arguments for the “common information” z, which is extracted from the triple
hxA , rA i, hxB , rB i, and hxC , rC i. We obtain that C(z) is not greater than the minimum of
I(xA , rA : xB , rB , xC , rC ),
I(xB , rB : xA , rA , xC , rA ),
I(xC , rC : xA , rA , xB , rB ),
1
2 [C(xA , rA ) + C(xB , rB ) + C(xC , rC ) − C(xA , rA , xB , rB , xC , rC )] .

(33)

Then we notice that for randomly chosen rA , rB , and rC , with probability 1 − ǫ the difference between
(33) and (27) is only O(log n/ǫ).
The general case: protocols with any number of rounds. The argument from the case of zero communication examined above easily relativizes: if Alice, Bob, and Charlie agree (after some communication)
on a common key z, and the transcript of the communication is t, then C(z | t) is not greater than the
minimum of
I(xA , rA : xB , rB , xC , rC | t),
I(xB , rB : xA , rA , xC , rC | t),
I(xC , rC : xA , rA , xB , rB | t),
1
2 [C(xA , rA | t) + C(xB , rB | t) + C(xC , rC | t) − C(xA , rA , xB , rB , xC , rC | t)] .

(34)

Let us prove that (34) is not greater than (33).
From the proof of Theorem 4.2 we known that the mutual information between parties’ data cannot not
increase when we relativize it on the transcript t. Thus, the first three quantities in (33) cannot become
greater when we add to these terms the transcript t as a condition.
18

It remains to prove a similar inequality between the information quantity
J(xA , xB , xC ) :=

1
[C(xA ) + C(xB ) + C(xC ) − C(xA , xB , xC )]
2

and its relativized version
J(xA , xB , xC | t) :=

1
[C(xA | t) + C(xB | t) + C(xC | t) − C(xA , xB , xC | t)] .
2

Notice that in general (for an arbitrary t) the inequality J(xA , xB , xC | t) ≤+ J(xA , xB , xC ) can be false.
So we need to employ the fact that t is the transcript of a communication protocol. Here we reuse the
technique from Theorem 4.2. We adapt the notion of a transcript-like function to the protocols with three
parties.
Definition 5.7 A set S ⊂ {0, 1}∗ × {0, 1}∗ × {0, 1}∗ is a combinatorial parallelepiped, if it can be represented as a Cartesian product S = A × B × C for some A, B, C ⊂ {0, 1}∗.
Definition 5.8 We say that a computable function f : {0, 1}∗ × {0, 1}∗ × {0, 1}∗ → {0, 1}∗ is transcriptlike, if for every t, the pre-image f −1 (t) is a combinatorial parallelepiped.
Similarly to the proof of Theorem 4.2, we will use the trick with “clones” of inputs. Let f be any
transcript-like function of three arguments. We fix a triple of strings (a, b, c) (of length at most n) and
denote t := f (a, b, c). We say that a string a′ is an A-clone of a (conditional on t), if
(i) there exist some strings b′ , c′ such that f (a′ , b′ , c′ ) = t, and
(ii) each coordinate of the extended complexity profile of (a′ , t) is not greater than the corresponding
coordinate of the extended complexity profile of (a, t).
Denote the sets of A-clones by ClonesA . Similarly, we define the set of B-clones of b (denoted ClonesB )
and C-clones of c (denoted ClonesC ), conditional on the fixed value t = f (a, b, c).
Claim 5.9 2C(a|f (a,b,c))−O(log n) ≤ |ClonesA | ≤ 2C(a|f (a,b,c))+1, 2C(b|f (a,b,c))−O(log n) ≤ |ClonesB | ≤ 2C(b|f (a,b,c))+1,
and 2C(c|f (a,b,c))−O(log n) ≤ |ClonesC | ≤ 2C(c|f (a,b,c))+1.
Proof is similar to the proof of Claim 4.7.
Lemma 5.10 If f : {0, 1}∗ × {0, 1}∗ × {0, 1}∗ → {0, 1}∗ is transcript-like function, then for all a, b, c we
have J(a, b, c | f (a, b, c)) ≤ J(a, b, c).
Proof Fix a, b, c and denote t := f (a, b, c). We choose a triple
(a′ , b′ , c′ ) ∈ ClonesA × ClonesB × ClonesC
that maximizes C(a′ , b′ , c′ | t). Due to the Claim above we have
C(a′ , b′ , c′ , t) =+
≥+

C(t) + log |ClonesA × ClonesB × ClonesC |
C(t) + C(a | t) + C(b | t) + C(c | t).

On the other hand, t can be deterministically computed as f (a′ , b′ , c′ ), so
C(a′ , b′ , c′ , t) ≤+ C(a′ ) + C(b′ ) + C(c′ ) ≤+ C(a) + C(b) + C(c).
Combining the last two inequalities we obtain
C(t) + C(a | t) + C(b | t) + C(c | t) ≤+ C(a) + C(b) + C(c),
which rewrites (assuming C(t | a, b, c) =+ 0) to
C(a | t) + C(b | t) + C(c | t) − C(a, b, c | t) ≤+ C(a) + C(b) + C(c) − C(a, b, c).
19

Hence, J(a, b, c | t) ≤ J(a, b, c), and the lemma is proven.
Now we conclude the proof of the theorem. Denote by π the function
′
′
′
π : hx′A , rA
i × hx′B , rB
i × hx′C , rC
i 7→ [the transcript of the protocol]

mapping the input data of Alice, Bob, and Charlie to the transcript of the communication protocol. This
is a transcript-like function (as the outcome of any communication protocol with three parties in the model
input in the hand ). So we can apply Lemma 5.10 to this mapping π, and we are done.
Remark 8 The inequality J(a, b, c | t) ≤+ J(a, b, c) can be easily proven in case when t is a deterministic
function of one of the arguments a, b or c. This observation (plus the idea to split the transcript t into
separate messages) essentially gives the proof of Theorem B.1 (for a constant number of rounds).
The case of ℓ > 3 parties. Let us sketch the proof of a general version of Theorem 5.5 for any constant
number of parties ℓ ≥ 3. To this end we should generalize the information quantity J(a, b, c) J(a, b, c | t)
defined above. We need to consider the s-valent version of J for all s = 2, . . . , ℓ,
J(x1 , x2 , . . . , xs ) :=
and
J(x1 , x2 , . . . , xs | t) :=


1 
C(x1 ) + . . . + C(xs ) − C(x1 , . . . , xs )
s−1


1 
C(x1 | t) + . . . + C(xs | t) − C(x1 , . . . , xs | t) .
s−1

(Observe that these quantities appear in (28).)
The notions of a transcript-like function can be extended to the functions with ℓ > 3 arguments. The
technique of “clones” permits to generalize Lemma 5.10 to this case. It follows that for all transcript-like
function f = f (x1 , x2 , . . . , xs ) it holds
J(x1 , x2 , . . . , xs | f (x1 , x2 , . . . , xs )) ≤ J(x1 , x2 , . . . , xs ).
Combining this observation with Proposition 5.4 we obtain the generalization of Theorem 5.5 for any number of parties ℓ > 3. We omit the details of this proof (which is a rather straightforward but cumbersome
generalization of the proof of Theorem 5.5).

5.3

Positive results for multi-party protocols

In this section we prove the positive statement: we describe a three parties protocol that on every input
tuple (xA , xB , xC ) produces with high probability a secret key of length
C(xA , xB , xC ) − CO(xA , xB , xC ) − O(log n)
assunimg that the parties are given the complexity profile of the input tuple.
Theorem 5.11 There exists a 3-party protocol for secret key agreement with the following characteristics:
(1) For every n, for every tuple (x1 , x2 , x3 ) of n-bit strings, for every ǫ > 0, if Alice’s input xA consists
of x1 , the complexity profile of the tuple and ǫ, Bob’s input xB consists x2 , the complexity profile of
the tuple and ǫ, and Charles’s input xC consists of x3 , the complexity profile of the tuple and ǫ, then
at the end the three parties compute with probability 1 − O(ǫ) a common string z such that
C(z | t) ≥ |z| − O(log(1/ǫ)) and |z| ≥ C(x1 , x2 , x3 ) − CO(x1 , x2 , x3 ) − O(log(n/ǫ)),
where t is the transcript of the protocol, and the constants in the O(·) notation depend only on the
universal machine.
(2) The protocol has 1 round.

20

Proof We first give an overview of the protocol.
In the first step, the three parties compute an optimal tuple (nA , nB , nC ) for the optimization problems
that defines CO(x1 , x2 , x3 ) (see Definition 5.1), and then Alice computes pA of length nA + O(log n), Bob
computes pB of length nB + O(log n), and Charles computes pC of length nC + O(log n), such that with
high probability (xA , pB , pC ) is a program for (x1 , x2 , x3 ), (pA , xB , pC ) is a program for (x1 , x2 , x3 ), and
(pA , pB , xC ) is a program for (x1 , x2 , x3 ). Next, Alice broadcasts pA , Bob broadcasts pB , and Charles
broadcasts pC . Alice also broadcasts a random string r of length O(log n) bits, which will be used in the
second step.
In the second step, each party computes (x1 , x2 , x3 ). Next, each party using the randomness r computes
a string z that with high probability is a short program for (x1 , x2 , x3 ) given (pA , pB , pC ). We will show
that z has the desired properties.
We proceed with the details.
Step 1. Using the complexity profile of (x1 , x2 , x3 ), each party computes a common tuple (nA , nB , nC )
which is optimal for the optimization problem that defines CO(x1 , x2 , x3 ) (there may be more optimal
tuples, but the parties agree on choosing the same tuple in some canonical way).
Next, Alice uses the encoding procedure E from Theorem 2.1 for ℓ = 2, on input x1 , nA , ǫ and obtains pA .
The length of pA is bounded by nA + O(log(n/ǫ)). Similarly, Bob and Charles obtain pB and respectively
pC , from x2 , nB , and respectively x3 , nC . The parties broadcast pA , pB , pC as indicated in the overview.
Step 2. Alice uses the decoding algorithm D from Theorem 2.1 for ℓ = 2, on input x1 , pB , pC . Since
nB , nC satisfy the Slepian-Wolf constraints (i.e., nB + nC ≥ C(xB , xC | xA ), nB ≥ C(xB | xA , xC ),
nC ≥ C(xC | xA , xB )), it follows that with probability 1 − O(ǫ), Alice can reconstruct x2 and x3 , and since
she has x1 , she obtains (x1 , x2 , x3 ). The similar facts hold for Bob and Charles. Therefore, with probability
1 − O(ǫ), each party obtains the tuple (x1 , x2 , x3 ), an event which henceforth we assume to hold.
For the next operation, the plan is to use the encoding procedure given in Theorem 2.2 and compute
a short program for (x1 , x2 , x3 ) given (pA , pB , pC ). For that, the parties need to have a tight upper bound
for C(x1 , x2 , x3 | pA , pB , pC ). Such an upper bound is provided in the following claim, which will be proved
later.
Claim 5.12 There exists a constant d such that
C(x1 , x2 , x3 | pA , pB , pC ) ≤ C(x1 , x2 , x3 ) − CO(x1 , x2 , x3 ) + d log n.
Now, using the upper bound provided by Claim 5.12, Alice (and also Bob, Charles) use the encoding
procedure from Theorem 2.2 and on input (x1 , x2 , x3 ), upper bound k = C(x1 , x2 , x3 ) − CO(x1 , x2 , x3 ) +
d log n and randomness r, computes a string z, of length |z| = k + c log(n/ǫ) for some constant c, that,
with probability 1 − O(ǫ) is a program for (x1 , x2 , x3 ) given (pA , pB , pC ). The transcript of the protocol is
t = (pA , pB , pC , r). We have
C(z | t) = C(z | pA , pB , pC , r) =+ C(z | pA , pB , pC ) (because |r| = O(log n))
≥+ C(x1 , x2 , x3 | pA , pB , pC ) (because z is a program for (x1 , x2 , x3 ) given pA , pB , pC )
=+ C(x1 , x2 , x3 ) − C(pA , pB , pC )
(because pA is computed from x1 and O(log n) bits, similarly for pB , pC )
≥+ C(x1 , x2 , x3 ) − (nA + nB + nC ) ( |pA | ≤+ nA , similarly for pB , pC )
= C(x1 , x2 , x3 ) − CO(x1 , x2 , x3 )
≥+ |z|,
which shows that z is a secret key with randomness deficiency O(log(n/ǫ)). Using randomness extractors
and an additional random string s broadcast by Alice in Step 1, similar to the proof of Theorem 4.1, the
randomness deficiency of z can be reduced to O(log(1/ǫ)).
It remains to prove Claim 5.12.
Proof(of Claim 5.12.) Suppose that Alice, Bob, and Charles know s = C(x1 , x2 , x3 | pA , pB , pC ).
Since each of x1 , x2 and x3 are n-bits long, C(x1 , x2 , x3 | pA , pB , pC ) ≤ 3n + O(1), and thus the length of
s in binary representation is bounded by log n + O(1) bits. Suppose s is given as part of the input, i.e.,
Alice’s input is (x1 , s) instead of just x1 , and similarly s is given to Bob and Charles. Then Alice, Bob
21

and Charles can use the encoding procedure given in Theorem 2.2: From (x1 , x2 , x3 ), the upper bound s
and the randomness r, they compute a string z ′ that, with probability 1 − 1/n is a program for (x1 , x2 , x3 )
given (pA , pB , pC ) and z ′ has length |z ′ | ≤ s + c log n = C(x1 , x2 , x3 | pA , pB , pC ) + c log n for some constant
c. We have
C(z ′ | pA , pB , pC )

≥ C(x1 , x2 , x3 | pA , pB , pC )
(because z ′ is a program for (x1 , x2 , x3 ) given (pA , pB , pC )
′
≥ |z | − c log n.

The transcript of the protocol (that uses s as part of the input) is t = (pA , pB , pC , r) and since the length of r
is only O(log n), it follows that C(z ′ | t) =+ C(z ′ | pA , pB , pC ) and therefore C(z ′ | t) ≥+ |z ′ |. It follows that
z ′ is a secret key that Alice, Bob, and Charles have obtained via the protocol with s added to the input. It
follows from Theorem 5.5 that we get the upper bound C(z ′ | t) ≤ C(x1 , x2 , x3 , s)−CO(x1 , x2 , x3 )+d′ log n,
for some constant d′ . Since s is only log n + O(1) bits long, we can drop s at the cost of increasing the
constant d′ . The conclusion follows, because C(x1 , x2 , x3 | pA , pB , pC ) ≤ C(z ′ | pA , pB , pC ) ≤ C(z ′ | t).
(End of proof of Claim 5.12.)

6

Communication complexity of secret key agreement

It is of interest to find the communication complexity for the task of finding a shared secret key having
the optimal length of I(x : y). We solve this problem in the model of randomized protocols with public
random bits, visible to Alice, Bob, and the adversary. This model is obtained by modifying slightly the
definition from Section 2.2 (in which the random bits are private): we require that rA = rB = r and we
change equation (3) to C(z | t, r) ≥ |z| − δ(n).
The protocol presented in the proof of Theorem 4.1 solves the task with communication min(C(x |
y), C(y | x)) + O(log n). As presented, that protocol uses private random bits but it can be easily modified
to work in the model with public randomness. Indeed, Alice and Bob use only O(log n) private random
bits. So if we make these bits known to the adversary, this will not affect much the secrecy of the common
key z produced in the protocol. That is, we still have the inequality
C(z | [everything known to the adversary]) ≥ |z| − O(log n),
only the constant in the term O(log n) becomes bigger (compared to equation (18)). Thus, the assumption
that all participants of the protocol have access to a public source of random bits, only makes the protocol
simpler, and with decreased communication complexity by O(log n).
We argue that within the model with public randomness the communication complexity of this protocol
is optimal, up to the O(log n) term. In what follows we assume as usual that Alice is given a string x and
Bob is given a string y, and both parties know the complexity profile of (x, y).
Theorem 6.1 Let ǫ, δ1 , δ2 be arbitrary positive real constants. There is no secret key agreement protocol
with public random bits such that for all inputs x and y,
1. the communication complexity of the protocol (the total number of all bits sent be Alice and Bob) is
less than (1 − δ1 ) min{C(x | y), C(y | x)},
2. Alice and Bob agree with probability > ǫ on a common key z such that C(z | t, r) > δ2 I(x : y), where
r is the public randomness and t = t(x, y, r) is the transcript of the protocol.
Specifying the parameters. To prove the theorem, we will find for each protocol a ‘hard’ pair (x, y),
on which this protocol fails. More specifically, we will show that any communication protocol with public
randomness fails on some pair with the profile
C(x) =+ 2n, C(y) =+ 2n, C(x, y) =+ 3n.
(for large enough n). Notice that (35) implies I(x : y) =+ n.
22

(35)

Remark 9 The construction that we present in this section can be adapted to construct a ‘hard’ pair (x, y)
with any given nontrivial complexity profiles (we only need that C(x|y) and C(y|x) are both not too small).
We could make Theorem 6.1 stronger by replacing the constant values δi by δi = λi log n/n with large
enough constant coefficients λi > 0 (i = 1, 2). We sacrifice the generality to simplify the notation.
Digression: common information. Before we prove Theorem 6.1, we remind some results on common
information. We say (somewhat informally) that strings x and y share k bits of common information, if
there exists a string w of complexity k such that w can be easily “extracted” from x and from y, i.e.,
C(w | x) ≈ 0 and C(w | y) ≈ 0. To make this statement formal, we must specify the precision of the
equalities C(w | x) ≈ 0 and C(w | y) ≈ 0. In the next definition we introduce a suitable notation.
Definition 6.2 We say that k bits of common information
(kA , kB ), if there exists a string w such that

≥
 C(w)
C(w | x) ≤

C(w | y) ≤

can be extracted from x and y with inaccuracies
k,
kA ,
kB .

Denote by ComInf(x, y) the set of all triples (k, kA , kB ) such that k bits of common information can be
extracted from x and y with inaccuracies (kA , kB ).
It is know that ComInf(x, y) is not uniquely defined by the complexity profile of (x, y). That is, pairs
(x, y) and (x′ , y ′ ) with very similar (or even identical) complexity profiles can have very different properties
of “extractability” of the mutual information, see [CMR+ 02]. Next theorem describes the minimal possible
set of triples ComInf(x, y) for a pair with complexity profile (35).
Theorem 6.3 [Muc98] For every δ > 0 and for all large enough n there exists a pair of strings (x, y) such
that C(x) =+ 2n, C(y) =+ 2n, C(x, y) =+ 3n, and no triple (k, kA , kB ) satisfying

 kA ≤ (1 − δ)n,
kB ≤ (1 − δ)n,

kA + kB + δn ≤ k
belongs to ComInf(x, y).
I. Razenshteyn proposed a more constructive version of Theorem 6.3. Though we cannot algorithmically
construct a pair (x, y) satisfying Theorem 6.3 (there is obviously no short algorithmic description of any
object of high Kolmogorov complexity), we can immerse such a pair in a large constructive set where the
majority of elements have the desired property:
Theorem 6.4 [Raz11] For every δ > 0 there exists an algorithm that for all large enough n generates
some list of pairs Sn such that for the majority of (x, y) ∈ Sn C(x) =+ 2n, C(y) =+ 2n, C(x, y) =+ 3n,
and no triple (k, kA , kB ) satisfying

 kA ≤ (1 − δ)n,
kB ≤ (1 − δ)n,

kA + kB + δn ≤ k
belongs to ComInf(x, y).

Remark 10 Technically, [Raz11] formulates Theorem 6.4 only in the symmetric setting kA = kB . However
Razenshteyn’s proof applies in the general case.
Remark 11 When we claim in Theorem 6.4 that an algorithm generates a set Sn , we mean that on the
input n the algorithm prints the list of elements of this set and stops. It is important that the enumeration
of Sn has a distinguishable completion.
The weak version of “constructiveness” that appear in Theorem 6.4 is called stochasticity, [She83]. An
individual string x is called (α, β)-stochastic, if there exists an algorithm of complexity < α that prints the
23

list of elements of a set S such that x ∈ S and C(x) ≥ log |S| − β. That is, if α and β are small, then an
(α, β)-stochastic string x is, so to say, a typical element in a simple set.
The notion of (α, β)-stochasticity can be easily adjusted to deal with pairs of strings. Thus, Theorem 6.4
asserts that there exist (O(log n), O(log n))-stochastic pairs with the worst possible extractability of the
mutual information.
On the uselessness of random oracles. In computability theory it is very common to study “relativized”
computations, i.e., computations with an oracle. In the theory of Kolmogorov complexity a natural version
of relativization consists in adding of an oracle (which can be a finite or infinite sequence of bits) to the
“condition” part of all complexity terms. So, the property of extracting of k bits of common information
from x and y with an oracle r can be formulated as follows: there exists a string w such that C(w | r) = k,
while C(w | x, r) ≈ 0 and C(w | y, r) ≈ 0. More generally, we define ComInf(x, y | r) as the set of all
triples (k, kA , kB ) such that

≥ k,
 C(w | r)
C(w | x, r) ≤ kA ,

C(w | y, r) ≤ kB .
If a string r is independent of (x, y), i.e., I(x, y : r) ≈ 0, then it seems natural to conjecture that all
reasonable properties of Kolmogorov complexity concerning (x, y) do not change if we relativize them with
r. In particular, it seems plausible that the difference between the sets ComInf(x, y|r) and ComInf(x, y)
must be negligible. Surprisingly, this conjecture remains unproven. However, a version of this conjecture
for stochastic pairs is known to be true.

Theorem 6.5 [MR10] If (x, y) is (O(log n), O(log n))-stochastic, then the set ComInf(x, y | r) belongs to
an O(log n)-neighborhood of ComInf(x, y) and vice-versa.
Now we are ready to prove Theorem 6.1.
Proof of Theorem 6.1. We fix some ǫ, δ1 , δ2 > 0. Assume for the sake of the argument that in a
protocol with communication complexity < (1 − δ1 )n, Alice and Bob agree with a probability greater than
ǫ on a common secret key z such that C(z | t, r) > δ2 n. In what follows we show that this assumption
leads to a contradiction. We will provide a counterexample, i.e., a pair (x, y) on which the protocol fails.
First we consider a degenerate case — a communication protocol without randomness.
(a) The case of deterministic protocols. At first we focus on a very special case: we assume that the
communication protocol is deterministic (Alice and Bob do not use the source of random bits). In this
case C(z | t, r) > δ2 n simplifies to C(z | t) > δ2 n.
Denote w := ht, zi. We look at this w as sort of “common information” extracted from x and y. Let us
estimate the parameters of this “shared part” of two strings.
• [a trivial calculation] C(w | x) ≤+ C(t) + C(z | t, x) ≤+ (1 − δ1 )n,
• [a similar calculation] C(w | y) ≤+ C(t) + C(z | t, y) ≤+ (1 − δ1 )n,
• [a less trivial but also straightforward calculation]
C(w)

=+
=+
≥+
≥+

C(w
C(w
C(w
C(w

| x) + C(w
| x) + C(w
| x) + C(w
| x) + C(w

| y) + I(x : y) − I(x : y | w)
[Appendix, Lemma A.9(a)]
| y) + I(x : y) − I(x : y | t) + C(z | t) [Appendix, Lemma A.9(b)]
| y) + C(z | t)
| y) + δ2 n.

For the transition from the second to the third line we used the inequality I(x : y) − I(x : y | t) ≥+ 0,
which can be false for arbitrary x, y, t. Fortunately, it is true if t is the transcripts of a communication
protocol with inputs x and y (Lemma 4.6).
We know from Theorem 6.3 that the three inequalities above cannot hold together, if (x, y) is a pair
with a minimal ComInf(x, y). Thus, we get a contradiction.
(b) Randomized protocols. Now we want to extend the result from the previous paragraph to randomized
protocol. We assume now that there exists a communication protocol with public random bits r such that
24

for most r the protocol produces a transcript t of size < (1 − δ1 )n that permits to extract from x and y a
common key z such that C(z | t, r) ≥ δ2 n.
Denote again w := ht, zi. Then the triple (C(w | r), C(w | x, r), C(w | y, r)) belongs to ComInf(x, y | r).
We can repeat the calculations from Case (a), adding the string r to the condition of all complexities:
• C(w | x, r) ≤+ (1 − δ1 )n,
• C(w | y, r) ≤+ (1 − δ1 )n,
• C(w | r) ≥+ C(w | x, r) + C(w | y, r) + δ2 n
We may assume that r is independent of (x, y), i.e., I(x, y : r) =+ 0. If (x, y) is a stochastic pair, then
from Theorem 6.5 it follows that (almost) the same triple of integers
(C(w | r) + O(log n), C(w | x, r) + O(log n), C(w | y, r) + O(log n))
must belong to ComInf(x, y). Due to Theorem 6.4 this is false for some stochastic (x, y), and we get a
contradiction.

7

Final comments

7.1

Time-efficient secret key agreement protocols.

The secret key agreement protocol in the proof of Theorem 4.1 is computable but highly non-efficient.
The only slow stage of the protocol is Step 2, where Bob reconstructs x given his input string y and the
fingerprint px|y obtained from Alice. At this stage Bob has to simulate all programs of size C(x | y) until
he obtains a string matching the fingerprint px|y . All other stages of the protocol can be implemented
in polynomial time (to this end we need to use an effective version of an extractor in the definition of
fingerprints; this increases the overhead in communication complexity from O(log n) to poly(log n), which
is still negligible comparative to the size of px|y ; for details see [Zim17]).
We cannot make Bob’s computation effective in general, but we can do it for some specific pairs of inputs
(x, y). Actually we can make the entire communication protocol fast, if there is a way to communicate x
from Alice to Bob so that
• communication complexity of this stage (and therefore the information revealed to the adversary)
remains about C(x | y),
• all computations are performed by Alice and Bob in time poly(n).
Example 1. (Discussed in Introduction, p. 1.) Let Alice get a random line x in the affine plane over the
finite field with 2n elements, and Bob get a random point y on this line. For most inputs of this type
we have C(x | y) = n ± O(log n), and there exists a simple way to transfer x from Alice to Bob with
communication complexity n (Alice just sends to Bob the slope of her affine line, and Bob draws a line
with this slope incident to his point). Thus, we see once again that for this simple example there exists an
effective (polynomial-time) communication protocol to agree on common secret key of size ≈ n bits.
Example 2. Let Alice and Bob get n-bits strings x and y respectively, and the Hamming distance
between these strings is at most δn for some constant δ < 1/2. For most inputs of this type we have
C(x | y) = h(δ)n ± O(log n), I(x : y) = (1 − h(δ))n ± O(log n),
1
. Can we transfer x from Alice to Bob with communication complexity
where h(δ) = δ log 1δ + (1 − δ) log 1−δ
h(δ)n + o(n) ? It turns out that such a protocol exists; moreover, there exists a communication protocol
with asymptotically optimal communication complexity and polynomial time computations, see [Smi07,
GS10, GS16]. Plugging this protocol in our proof of Theorem 4.2 we conclude that on most pairs of inputs
(x, y) of this type Alice and Bob can agree on a common secret key of size (1−h(δ))n−o(n), with poly-time
computations for both parties.

25

7.2

Secret key agreement with an additional private communication channel

In this section we discuss a slightly more general model of communication that combines a public and
a private channels. We assume that the private communication channel is not visible to the adversary.
There is a naive and straightforward way to gain from such a channel: Alice tosses her private random
coin, sends the obtained bits to Bob via this private channel, and afterwards Alice and Bob can use these
bits as a common secret key. This naive idea is actually the optimal usage of the private channel. There is
no better way to use the secret communication: if Alice and Bob are given strings x and y, and they send
to each other s bits of information via the private communication, they cannot agree (with probability
1 − ǫ) on a common secret key of complexity greater than I(x : y) + s + O(log(n/ǫ)). Indeed, denote by tp
the transcript of the communications via the private channel. Then the common secret z can be computed
from (xA , rA , tp ) as well as from (xB , rA , tp ). It follows that
C(z) ≤+
≤+
≤
≤

C(z | xA , rA , tp ) + C(z | xB , rB , tp ) + I(xA , rA , tp : xB , rB , tp )
I(xA , rA , tp : xB , rB , tp ) ≤+ I(xA , rA : xB , rB ) + C(tp )
I(xA : xB ) + C(tp ) + O(log(n/ǫ))
I(xA : xB ) + s + O(log(n/ǫ))

(the third inequality holds with probability 1 − ǫ).
Let us consider now a model where Alice and Bob communicate via two channels: via an ‘expensive’
private channel of capacity s bits and a ‘cheap’ public channel of unbounded capacity (accessible to the
adversary). As above, let xA and xB be input strings of length n on which the protocol succeeds with error
probability ǫ and randomness deficiency δ(n) = O(log n), and let z be the random string that is the shared
secret key output by the protocol, i.e., a string satisfying relations (2) and (3). We combine the simple
observation above with the proof of Theorem 4.2 and conclude with the following result: with probability
at least 1 − O(ǫ), if n is sufficiently large, |z| ≤ I(xA : xB ) + s + O(log(n/ǫ)).
The ‘light upper bound’ from Section 3 does not apply to the model with an additional private channel.
Actually, the traffic of size s over the private channel can be counted as an overhead in Lemma 3.1; then
in (16) we would need to count s bits of the overhead for each round of communication via the public
channel. For a k-round protocol this would give the bound |z| ≤ I(xA : xB ) + ks + O(log(n/ǫ)), which is
too weak for non-constant k.
We revisit these observations in Section 7.3.

7.3

Secret key agreement: the Shannon framework vs. the Kolmogorov framework

Upper and lower bounds on the size of the shared secret key. In the Introduction we discussed
the general connections between IT and AIT. In what follows we discuss some more precise and formal
relations between Shannon-type and Kolmogorov-type theorems on secret key agreement.
Actually the upper and lower bounds on the size of the common key in the framework of Kolmogorov
complexity (Theorem 4.1 and Theorem 4.2) formally imply similar bounds in Shannon’s framework for i.i.d.
pairs variables and even for stationary ergodic sources (Theorem 1 in [Tya13], see also [LYC76, BBR88,
Mau93, AC93]). Indeed, it is well known that a sequence of i.i.d. random variables (or, more generally, the
outcome of a stationary ergodic source) gives with a high probability a string of letters whose Kolmogorov
complexity is close to Shannon’s entropy of the random source, [MV14, Hor03]. Hence, if Alice gets a
value of (X1 , . . . , Xn ), Bob gets a value of (Y1 , . . . , Yn ), and the sequence of pairs (Xi , Yi ) is a stationary
ergodic source, then with high probability the mutual information (in the sense of Kolmogorov complexity)
between Alice’s and Bob’s individual inputs is close to the mutual information between these two random
sequences (in the sense of Shannon’s entropy).
Thus, to prove the positive statement in Shannon’s framework (Alice and Bob can agree on a secret
key of size about I(X1 , . . . , Xn : Y1 , . . . , Yn )) we can apply the communication protocol from the proof
of Theorem 4.1. Notice that in Theorem 4.1 Alice and Bob need to know the complexity profile of the
input data; we cannot know the exact values of Kolmogorov complexity for a pair of randomly chosen
random strings, but it is enough to provide Alice and Bob with the known expected value of the complexity
26

profile of their input data (see Remark 3 on p. 13). In the case when the complexity profile of the values
of X1 , . . . , Xn and Y1 , . . . , Yn is ‘typical’ (close to the average values), Theorem 4.1 guarantees that the
resulting common key z has a large enough Kolmogorov complexity conditional on the transcript of the
protocol. Otherwise (in case when the complexity profile of the input data is not typical) the result of the
protocol can be meaningless; however, this happens with only a small probability. So, assuming that Alice
and Bob are given random values of X1 , . . . , Xn and Y1 , . . . , Yn respectively, we conclude that the outcome
of the protocol (the common secret key) is distributed mostly on strings of high Kolmogorov complexity.
It is not hard to show that such a distribution must have Shannon’s entropy (conditional on the value of
the transcript) close to I(X1 , . . . , Xn : Y1 , . . . , Yn ).
In a similar way our negative result (the secret common key cannot be made bigger, Theorem 4.2)
implies a similar result in Shannon’s setting. Indeed, assume that there exists a communication protocol
that permits to Alice and Bob to agree on a common secret on random inputs X1 , . . . , Xn and Y1 , . . . , Yn
with a probability close to 1. If the pair of random sources is stationary and ergodic, then with high
probability the pair of input values has a complexity profile close to the corresponding values of Shannon’s
entropy. It follows from Theorem 4.2 that Kolmogorov complexity of the secret key is not much bigger than
the mutual information between X1 , . . . , Xn and Y1 , . . . , Yn . It remains to notice that Shannon’s entropy
of the common secret key Z (as a random variable) cannot be much bigger than the average Kolmogorov
complexity of its value (as a binary string).
In Shannon’s framework we can consider a hybrid communication model (similar to those in Section 7.2)
where Alice and Bob can communicate via a private channel of bounded capacity (hidden from the adversary) and a public channel of unbounded capacity (accessible to the adversary). The connection between
Shannon’s and Kolmogorov’s settings discussed above combined with the observation made in Section 7.2
implies that in this model Alice and Bob cannot agree on a common secret key of entropy greater than
I(X1 , . . . , Xn : Y1 , . . . , Yn ) + [capacity of the private channel].
Communication complexity of the protocol. Another issue that can be studied in both settings
(for Shannon’s and Kolmogorov’s approaches to the key agreement problem) is the optimal communication
complexity of the protocol. Tyagi investigated in [Tya13] this problem for the Shannon’s framework (for
i.i.d. sources) and showed that in some cases (for some distributions (Xi , Yi )) Alice and Bob need to send
to each other at least
min(H(X1 , . . . , Xn | Y1 , . . . , Yn ), H(Y1 , . . . , Yn | X1 , . . . , Xn ))
bits of information to agree on a common secret key of size I(X1 , . . . , Xn : Y1 , . . . , Yn ). Moreover, Tyagi
found a complete description (so-called one letter characterization) of the optimal communication complexity for an arbitrary distribution on Alice’s and Bob’s inputs. This result is similar to our Theorem 6.1,
which claims that Alice and Bob need to send at least min(C(x | y), C(y | x)) bits of information to agree
even on a common secret key of size δI(x : y). However, these results are incomparable with each other
(one does not follow from another):
• Tyagi investigated protocols that agree on a common secrets of maximal size I(X1 , . . . , Xn : Y1 , . . . , Yn ),
while Theorem 6.1 applies even if Alice and Bob agree on a secret of size δI(x : y) for a small δ > 0.
• [Tya13] proposed a one letter characterization of the communication complexity in terms of the
distribution (Xi , Yi ), which arguably cannot be reformulated in the setting of Kolmogorov complexity.
• The result in [Tya13] applies to communication protocols with private randomness, while Theorem 6.1
is proven only for protocols with public randomness.
One-shot paradigm. Most known results on the protocols for secret key agreement in Shannon’s
framework are proven with the assumption that the input data available to Alice and Bob are i.i.d. random variables or at least stationary ergodic random sources. We mentioned above that for this class of
inputs (stationary ergodic random sources) the bounds on the optimal size of the secret in Shannon’s
framework can be deduced from analogous results on Kolmogorov complexity. But actually Theorem 4.1
27

and Theorem 4.2 appliy in more general settings. We can prove similar bounds for random inputs obtained
in one shot, without the property of ergodicity.
In many natural instances of the secret key agreement problem the input data are far from being ergodic,
so the classic technique does not apply. In Section 7.1 we discussed two examples of this kind: in the first
one, Alice is given a line in the affine plane, and Bob is given a point in this line; in the second one, Alice
and Bob get n-bits strings x and y respectively, and the Hamming distance between these strings is at most
δn for some constant δ < 1/2. These examples can be naturally reformulated in the probabilistic setting:
we can introduce the uniform distribution on the set of all valid pairs of inputs. For the probabilistic
versions of these examples the matching upper and lower bounds on the size of the common secret key can
be easily deduced from Theorem 4.1 and Theorem 4.2.
We notice in conclusion that the standard results on the secret key agreement deal with the paradigm the
protocol works properly for most randomly chosen inputs (which is typical for the information theory), while
in our approach we prove a somewhat stronger statement : for each valid pair of input data the protocol
works properly with high probability (which is typical for the theory of communication complexity).

7.4

Open problems

Open Question 1 In Theorem 6.1 we establish a lower bound on how many bits Alice and Bob must
communicate to agree on a common secret key. Our proof is valid only for communication protocols with
public randomness. Is the same bound true for protocols with private sources of random bits?
Open Question 2 All our communication protocols are randomized. It is natural to ask whether we can
get rid of external randomness. We conjecture that for (O(log n), O(log n))-stochastic tuples of inputs the
protocol can be made purely deterministic (though it would require very high computational complexity),
but this cannot be done in the general case. The proof of this fact would require a better understanding
of the nature of non-stochastic objects (such as Chaitin’s Omega number, [Cha75], see also [She83] and
[SUV17]).

8

Acknowledgments

We are grateful to Bruno Bauwens for his insightful comments. In particular we thank him for allowing
us to reproduce his proof of the “light lower bound” in Section 3 and for bringing to our attention the
improved Kolmogorov complexity version of the Slepian-Wolf theorem 2.1. We thank Tarik Kaced for
attracting our attention to [CABE+ 15].

References
[AC93]

Rudolf Ahlswede and Imre Csiszár. Common randomness in information theory and cryptography - I: secret sharing. IEEE Trans. Information Theory, 39(4):1121–1132, 1993.

[ALPS10]

Luis Antunes, Sophie Laplante, Alexandre Pinto, and Liliana Salvador. Cryptographic security
of individual instances. ICITS, pages 195–210, 2010.

[Bau18]

Bruno Bauwens. Optimal probabilistic polynomial time compression and the slepian-wolf
theorem: tighter version and simple proofs. arXiv preprint arXiv:1802.00750, 2018.

[BBR88]

Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert. Privacy amplification by public
discussion. SIAM Journal on Computing, 17(2):210–229, 1988.

[BZ14]

Bruno Bauwens and Marius Zimand. Linear list-approximation for short programs (or the
power of a few random bits). In IEEE 29th Conference on Computational Complexity, CCC
2014, Vancouver, BC, Canada, June 11-13, 2014, pages 241–247. IEEE, 2014.

28

[CABE+ 15] Chung Chan, Ali Al-Bashabsheh, Javad B Ebrahimi, Tarik Kaced, and Tie Liu. Multivariate
mutual information inspired by secret-key agreement. Proceedings of the IEEE, 3(10):1883–
1913, 2015.
[Cha66]

Gregory J. Chaitin. On the length of programs for computing finite binary sequences. Journal
of the ACM, 13:547–569, 1966.

[Cha75]

Gregory J Chaitin. A theory of program size formally identical to information theory. Journal
of the ACM (JACM), 22(3):329–340, 1975.

[CK78]

Imre Csiszár and János Körner. Broadcast channels with confidential messages. IEEE Trans.
Information Theory, 24(3):339–348, 1978.

[CMR+ 02] Alexey V. Chernov, Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, and
Nikolai K. Vereshchagin. Upper semi-lattice of binary strings with the relation ”x is simple
conditional to y”. Theor. Comput. Sci., 271(1-2):69–95, 2002.
[CN04]

Imre Csiszár and Prakash Narayan. Secrecy capacities for multiple terminals. IEEE Trans.
Information Theory, 50(12):3047–3061, 2004.

[GK73]

Peter Gács and János Körner. Common information is far less than mutual information. Probl.
Control Inf. Theory, 2(2):149–162, 1973.

[GS10]

Venkatesan Guruswami and Adam Smith. Codes for computationally simple channels: Explicit
constructions with optimal rate. Foundations of Computer Science (FOCS), 2010 51st Annual
IEEE Symposium on, (723–732), 2010.

[GS16]

Venkatesan Guruswami and Adam Smith. Optimal rate code constructions for computationally simple channels. Journal of the ACM (JACM), 63(4):35, 2016.

[Hor03]

Yasuichi Horibe. A note on Kolmogorov complexity and entropy. Applied mathematics letters,
16(7):1129–1130, 2003.

[Kol65]

Andrei Nikolaevich Kolmogorov. Three approaches to the quantitative definition of information. Problems Inform. Transmission, 1(1):1–7, 1965.

[KR13]

Tarik Kaced and Andrei Romashchenko. Conditional information inequalities for entropic and
almost entropic points. IEEE Transactions on Information Theory, 59(11):7149–7167, 2013.

[KRV15]

Tarik Kaced, Andrei Romashchenko, and Nikolay Vereshchagin. Conditional information
inequalities and combinatorial applications. arXiv preprint arXiv:1501.04867, 2015.

[LYC76]

Sik Kow Leung-Yan-Cheong. Multi-user and wiretap channels including feedback, July 1976.
Tech. Rep. No. 6603-2, Stanford Univ.

[Mau92]

Ueli M. Maurer. Conditionally-perfect secrecy and a provably-secure randomized cipher. Journal of Cryptology, 5(1):53–66, 1992.

[Mau93]

Ueli M. Maurer. Secret key agreement by public discussion from common information. IEEE
Trans. Information Theory, 39(3):733–742, 1993.

[MR10]

Andrei A. Muchnik and Andrei E. Romashchenko. Stability of properties of Kolmogorov
complexity under relativization. Problems of information transmission, 46(1):38–61, 2010.

[Muc98]

Andrei A. Muchnik. On common information. Theor. Comput. Sci., 207:319–328, 1998.

[MV14]

Li Ming and Paul M.B. Vitányi. Kolmogorov complexity and its applications. Elsevier, 2014.

[Raz11]

Ilya Razenshteyn. Common information revisited. arXiv preprint arXiv:1104.3207, 2011.

[Rom00]

Andrei Romashchenko. Pairs of words with nonmaterializable mutual information. Problems
of Information Transmission, 36(1):3–20, 2000.
29

[She83]

Alexander Kh. Shen. The concept of (α, β)-stochasticity in the Kolmogorov sense, and its
properties. Soviet Math. Dokl., 28(1):295–299, 1983.

[Smi07]

Adam D. Smith. Scrambling adversarial errors using few random bits, optimal information
reconciliation, and better private codes. Symposium on Discrete Algorithms: Proceedings of
the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 7(09):395–404, 2007.

[Sol64]

Ray J. Solomonoff. A formal theory of inductive inference. Information and Control, 7:224–
254, 1964.

[SUV17]

Alexander Shen, Vladimir Uspensky, and Nikolay Vereshchagin. Kolmogorov complexity and
algorithmic randomness. American Mathematical Society, 2017.

[Tya13]

Himanshu Tyagi. Common information and secret key capacity. IEEE Transactions on Information Theory, 59(9):5627–5640, 2013.

[Vad12]

Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 2012.

[Wyn75]

Aaron D. Wyner. The wire-tap channel. Bell Syst. Tech J., 54(8):1355–1387, 1975.

[Zim17]

Marius Zimand. Kolmogorov complexity version of Slepian-Wolf coding. In STOC 2017, pages
22–32. ACM, June 2017.

A

Appendix

A.1

Proof of Lemma 4.3

Let us fix a z̃ and t that satisfy the relations (18). We introduce some notation:
n′ = |z̃|,

t̃ = (t, n′ , ǫ),

α = C(z̃ | t̃).

For some constant c we have
C(z̃ | t̃) ≥ |z| − c log(n/ǫ).
Let k = |z̃| − c log(n/ǫ). Thus, C(z̃ | t̃) ≥ k.
′
We use E : {0, 1}n × {0, 1}d → {0, 1}m, a (k − c1 , ǫ)- strong extractor (for some constant c1 that will
be specified later), having m = k − c1 − 2 log(1/ǫ) − O(1) and d = log n′ + 2 log(1/ǫ) + O(1).
In the following lemmas, s is a seed of the above strong extractor E chosen uniformly at random and
z = E(z̃, s).
Lemma A.1 With probability 1 − O(ǫ) over the choice of s,
C(z̃, s | t̃, α) ≤ C(z, s | t̃) + C(z̃ | t̃) − m + log(1/ǫ) + O(1).
Lemma A.2 With probability 1 − O(ǫ) over the choice of s,
C(z̃, s | t̃, α) ≥ C(z̃ | t̃, α) + |s| − O(log(1/ǫ)) − O(1).
Lemma A.3 C(z̃ | t̃, α) ≥ C(z̃ | t̃) − O(1).
Lemma A.4 For every s, C(z, s | t̃) ≤ |s| + C(z | s, t̃) + O(1).
Combining the four lemmas, we obtain that, with probability 1 − O(ǫ), C(z | s, t̃) ≥ m − O(log(1/ǫ)) −
O(1). Since |z| = m = I(x : y) − O(log n) − O(log(1/ǫ)), we obtain C(z | t, s) ≥ |z| − O(log(1/ǫ)) − O(1),
and that the length of z is I(x : y) − O(log n) − O(1/ǫ).
It remains to prove the lemmas.
′

Proof of Lemma A.1. Recall that the function E1 : {0, 1}n × {0, 1}d → {0, 1}d × {0, 1}m defined
by E1 (w, s) = (s, E(w, s)) is a (k − c1 , ǫ) extractor. We view E1 also as a bipartite graph, where the set
30

′

of left nodes is {0, 1}n , the set of right nodes is {0, 1}d × {0, 1}m, and (w, (s, z)) is an edge if E(w, s) = z
(or, equivalently, E1 (w, s) = (s, z)). Let
′

B = {w ∈ {0, 1}n | C(w | t̃) ≤ C(z̃ | t̃}.
m
We say that a right node (s, z) in the above graph is heavy, if its B-degree is ≥ (1/ǫ) |B|
M , where M = 2
(the B-degree of a node is the number of edges coming from B into the node). Let HEAVY be the set of
nodes that are heavy. By counting from the left and also from the right the edges that go out from B, we
get
|B|
≤ |B| · D,
|HEAVY| · (1/ǫ) ·
M
and therefore,
|HEAVY|
≤ ǫ.
M ·D

A left node w ∈ B is poor if for more than 2ǫ fraction of s ∈ {0, 1}d, E1 (w, s) is heavy.
Claim A.5 The number of poor nodes is less than 2k−c1 .
Proof Let POOR be the set of poor nodes. Since
Prob(E1 (UPOOR , U{0,1}d ) ∈ HEAVY)

> 2ǫ
+ ǫ,
≥ |HEAVY|
M·D

the number of poor nodes has to be less than 2k−c1 because otherwise the extractor property of E1 would
be contradicted.
Claim A.6 z̃ is not poor.
Proof Suppose z̃ is poor. Then C(z̃ | t̃, α) ≤ k − c1 , because, given t̃, α, the string tz is described by its
index in a canonical enumeration of B and the size of B is bounded by 2k−c1 (by Claim A.5). It is known
that for any z ′ , t′ , C(z ′ | t′ , C(z ′ | t′ )) ≥ C(z ′ | t′ ) − O(1) (this is the relativized version of the known
inequality C(z ′ | C(z ′ )) ≥ C(z ′ ) − O(1), see [SUV17, Exercise 44]). It follows that
C(z̃ | t̃) ≤ C(z̃ | t̃, α) + O(1) ≤ k − c1 + O(1).

(36)

On the other hand, C(z̃ | t̃) ≥ k. If c1 is large enough, we get a contradiction.
Claim A.6 says that for a fraction of 1−2ǫ of s ∈ {0, 1}d, the node (s, p) is non-heavy, where z = E(z̃, s).
If (s, z) is non-heavy, then the number of its left neighbors in B is bounded by
(1/ǫ)

2C(z̃|t̃)+1
|B|
≤ (1/ǫ)
= 2C(z̃|t̃)−m+log(1/ǫ)+1 .
M
M

It follows that, given t̃, α, z̃ can be described by a non-heavy (s, z) and its index in an enumeration of the
left nodes of (s, z) in B. Thus, with probability 1 − 2ǫ over the choice s,
C(z̃, s | t̃, α) ≤ C(z, s | t̃) + (C(z̃ | t̃) − m + log(1/ǫ) + 1) + O(1).
This concludes the proof of the lemma.
Proof of Lemma A.2. Let w = C(z̃ | t̃, α) + |s| − C(z̃, s | t̃, α). Note that w is a random variable
because it depends on s. We need to show that w = O(log(1/ǫ)), with probability 1 − ǫ.
By the standard counting argument, we have that with probability 1 − ǫ,
C(s | t̃, α) ≥ |s| − log(1/ǫ).

(37)

Let us fix an s that satisfies inequality (37). We show that the w that corresponds to this s satisfies
w = O(log(1/ǫ)), from which the conclusion follows.
31

If w ≤ 0, we are done. So let us suppose that w > 0.
Let u = C(z̃, s | t̃, α) = C(z̃ | t̃, α) + |s| − w = (α − O(1)) + |s| − w (the last equality holds because
C(z̃ | t̃, α) = C(z̃ | t̃) − O(1), by the first part of inequality (36)).
Let A = {(z ′ , s′ ) | C(z ′ , s′ | t̃, α) ≤ u}. Note that |A| ≤ 2u+1 . For every z ′ , we define Az′ = {s′ |
′ ′
(z , s ) ∈ A}. Let e be the integer for which 2e−1 < |Az̃ | ≤ 2e . Since s ∈ Az̃ and Az̃ can be enumerated
given w, t̃, α and O(1) bits, it follows that
C(s | t̃, α) ≤ e + 2 log w + O(1).

(38)

Let H = {z ′ | |Az̃ | > 2e−1 }. Note that |H| ≤ |A|/2e−1 ≤ 2u−e+2 and that z̃ is in H. We can write the
index of z̃ in an enumeration of H on exactly u − e + 2 bits and taking into account that u can be computed
from z̃, α, w and O(1) bits, it follows that e can be derived as well from the index of z̃ and the information
mentioned above. In this way we have all the information needed to enumerate H and we obtain
C(z̃ | t̃, α) ≤ u − e + 2 + 2 log w + O(1).

(39)

Adding inequalities (38) and (39), we get
C(z̃ | t̃, α) + C(s | t̃, α)

≤ u + 4 log w + O(1)
≤ (C(z̃ | t̃, α) + |s| − w) + 4 log w + O(1).

Taking into account inequality (37), we obtain w−4 log w ≤ log(1/ǫ)+O(1), which implies w = O(log(1/ǫ)),
as desired.
Proof of Lemma A.3. This is the first part in the chain of inequalities (36).
Proof of Lemma A.4. This follows from the fact that given t̃ (which contains n′ ) we can find the
length of s, and therefore we do not need delimiters to concatenate s and a description of z given s and t̃.

A.2

Useful information inequalities

Lemma A.7 Let f be a computable function, and suppose that for every string x, we choose a string r
uniformly at random among the strings of length f (|x|). Then,
(1) With probability 1 − ǫ,
C(x, r) − (C(x) + C(r | x)) ≤ O(log(|x|/ǫ)).
(2) With probability 1 − ǫ,
C(x, r) − (C(r) + C(x | r)) ≤ O(log(|x|/ǫ)).
and
(3) With probability 1 − ǫ,
C(x, r) = C(x) + |r| ± O(log(|x|/ǫ)).
Proof Note that part (3) follows, after a rescaling of ǫ, from part (1) and the fact that with probability
1 − ǫ, C(r | x) ≥ |r| − log(1/ǫ).
We prove (1). The proof of (2) is similar.
Clearly, C(x, r) ≤ C(x) + C(r | x) + 2 log |x| + O(1) by using the standard way of appending two strings
in a self-delimiting manner.
For the other inequality, we tweak the proof of the chain rule. We fix x and r and let t = C(x, r) −
|r| + log(1/ǫ). By the standard counting argument, with probability 1 − ǫ, t is positive, which we assume
from now on. Since C(x, r) ≤ |x| + |r| + 2 log |x| + O(1) and C(x, r) = t + |r| − log(1/ǫ), we get t ≤
|x| + 2 log |x| + log(1/ǫ) + O(1), and from here log t ≤ O(log(|x|/ǫ)), a fact which we will use later.
Now, let A = {(x′ , r′ ) | C(x′ , r′ ) ≤ t + |r|}. For each x′ , let Ax′ = {r′ | (x′ , r′ ) ∈ A}. Let e be such that
e−1
2
< |Ax | ≤ 2e . Note that by taking into account that |r| = f (|x|),
C(r | x) ≤ e + 2 log t + O(1).
32

(40)

Next, let H = {x′ | Ax′ > 2e−1 }. We have |H| ≤ |A|/2e−1 ≤ 2t+|r|+1 /2e−1 = 2t+|r|−e+2 . Note that x
can be described by its rank in an enumeration of H, and for the enumeration of H we need t and e. By
writing the rank of x on exactly t + |r| − e + 2 bits, and keeping in mind that |r| can be computed from
|x|, we obtain
C(x) ≤ t + |r| − e + 2 + 2 log t + 2 log |x| + O(1).
(41)
By adding equations (40) and (41), we obtain C(x) + C(r | x) ≤ t + |r| + 4 log t + 2 log |x| + O(1). Therefore
C(x, r)

= t + |r| − log(1/ǫ)
≥ C(x) + C(r | x) − 4 log t − 2 log |x| − log(1/ǫ) − O(1)
≥ C(x) + C(r | x) − O(log(|x|/ǫ)).

Lemma A.8 For all xA , xB , z, C(z) ≤+ C(z | xA ) + C(z | xB ) + I(xA : xB ).
Proof For all xA , xB , z we have
C(xA , xB | z) ≤+ C(xA | z) + C(xB | z).
We add 2C(z) to both sized of this inequality and get
C(z) + C(xA , xB , z) ≤+ C(xA , z) + C(xB , z).
Now we make it slightly weaker,
C(z) + C(xA , xB ) ≤+ C(xA , z) + C(xB , z).
It follows
C(z) ≤+ C(z | xA ) + C(z | xB ) + C(xA ) + C(xB ) − C(xA , xB ),
which is equivalent to (7).
Lemma A.9 (a) For all strings w, x, y of length O(n)
C(w | x) + C(w | y) + I(x : y) − I(x : y | w) − C(w | x, y) =+ C(w)
(b) For all strings x, y, z, t of length O(n), if C(z | x, t) =+ C(z | y, t) =+ 0, then
I(x : y | z, t) =+ I(x : y | t) − C(z | t)
Proof (a) A straightforward calculation gives
C(w | x) + C(w | y) + I(x : y) − I(x : y | w) − C(w | x, y)
=+ C(x, w) − C(x) + C(y, w) − C(y) + C(x) + C(y) − C(x, y)
− C(x, w) − C(y, w) + C(x, y, w) + C(w) − C(x, y, w) + C(x, y) = C(w)
(b) We have
I(x : y | z, t) =+ C(x, z, t) + C(y, z, t) − C(x, y, z, t) − C(z, t)
=+ C(x, t) + C(y, t) − C(x, y, t) − C(z, t)
since C(z | x, t) =+ C(z | y, t) =+ 0
+
= C(x, t) + C(y, t) − C(x, y, t) − C(t) − C(z | t)
the chain rule
=+ I(x : y | t) − C(z | t)

33

A.3

Proof of Lemma 5.6

For all xA , xB , xC , z we have
C(xA , xB , xC | z) ≤+ C(xA | z) + C(xB | z) + C(xC | z),
which rewrites to
2C(z) + C(xA , xB , xC , z) ≤+ C(xA , z) + C(xB , z) + C(xC , z).
Now we use the assumption that z is a deterministic function of xA , of xB , and of xC :
2C(z) ≤+ C(xA ) + C(xB ) + C(xC ) − C(xA , xB , xC ),
and the lemma is proven.

A.4

Communication protocols with logarithmic advice

In this section we show that in some setting the ‘light upper bound’ in Section 3 is more robust and flexible
than the more technical proof of Theorem 4.2.
Despite many prominent parallels between Shannon’s and Kolmogorov’s variants of information theory,
there is no canonical way to translate the basic properties from one framework to another. The rule of
thumb is to substitute Kolmogorov complexity instead of Shannon’s entropy and to change all constraints
of type ‘a random variable X is a function of a random variable Y ’ in Shannon’s case to ‘a string x has
small Kolmogorov complexity conditional on y’ in Kolmogorov’s version. For example, the classic Slepian–
Wolf theorem claims substantially that for jointly distributed X, Y (that technically must be a sequence
of i.i.d. pairs) there exists another random variable Z such that

 Z is a deterministic function of X,
number of bits in Z ≈ H(X | Y ),

X can be recovered from Y and Z with high probability.
The counterpart of this result for Kolmogorov complexity is known as Muchnik’s theorem, [Muc98]: for all
strings x, y of length n there exists a string z such that

 C(z | x) = O(log n),
|z| = C(x | y) + O(log n),

C(x | y, z) = O(log n).
We can use a similar logic to translate in the language of Kolmogorov complexity the general notion of an
interactive communication protocol. A protocol adapted to the framework of Kolmogorov complexity can
be viewed as a protocol where on each step Alice and Bob get logarithmic ‘advice’ strings from a trustable
Merlin.
In what follows we give a more formal definition of a protocol with advice bits. Let k be a positive
integer. We say that Alice and Bob given inputs xA an xB compute a common value z in a k-rounds
protocol with q bits of advice on each round, given inputs xA and xB , if there exists is a sequence of strings
(‘messages’) x1 , y1 , x2 , y2 , . . . , xk , yk such that
C(x1 | xA ) ≤ q,
C(y1 | xB , x1 ) ≤ q,
C(x2 | xA , x1 , y1 ) ≤ q,
C(y2 | xB , x1 , y1 , x2 ) ≤ q,
..
.
C(xk | xA , x1 , y1 , . . . , xk−1 , yk−1 ) ≤ q,
C(yk | xB , x1 , y1 , . . . , xk−1 , yk−1 ) ≤ q,
C(z | xA , x1 , y1 , . . . , xk , yk ) ≤ q,
C(z | xB , x1 , y1 , . . . , xk , yk ) ≤ q.
34

In a similar way we can define the randomized protocols with advice, where Alice and Bob are given in
addition random rA and rB . For c > 0, ǫ > 0 we say that Alice and Bob (ǫ, c)-succeed on an input pair
(xA , xB ) to agree on a common secret key in a k-rounds protocol with q bits of advice, if with probability
(1 − ǫ) over rA , rB , there exists a string z such that
C(z | t) ≥+ |z| − c log n,
where t := (x1 , y1 , . . . , xk , yk ) is a transcript of the protocol with advice defined above.
Any conventional communication protocol (without advice) can serve as a protocol with advice strings
of size q = O(1), so the lower bound from Theorem 4.1 remains true in the new setting. Also the proof
of the ‘light’ upper bound form Section 3 applies to the protocols with advice strings of size q = O(log n),
and we conclude that in the new setting Alice and Bob still cannot agree on a common secret key of size
greater than I(xA : xB ). Notice that the proof of Theorem 4.2 does not apply to protocol with advice,
so we cannot extend this upper bound to non-constant number of protocols. But this is not a real loss:
the protocols with advice probably make no sense for non-constant number of rounds (since too much
information can be hidden in the bits of advice).

B

Weak version of negative results for multi-party protocols

In this section we prove a weak version of the upper bound on the length of the longest secret key that
three parties can agree upon. The proposed argument follows the ideas from the proof of a similar result
in [CN04] in Shannon’s setting (it is based on classic information inequalities). While this technique works
pretty well in IT, in our case it covers only the protocol with O(1) rounds and with the number of random
bits bounded polynomially in the input length. Thus, the result proven in this section is much weaker than
Theorem 5.5. However, it may be instructive to see how far we can go in the setting of AIT while using
the classic technique borrowed from IT.
Theorem B.1 Let us consider a 3-party protocol for secret key agreement with error probability ǫ, having
a constant number of rounds, and where the number of random bits is bounded polynomially in the input
length. Let (xA , xB , xC ) be a 3-tuple of n-bit strings on which the protocol succeeds. Let z be the random
variable which represents the secret key computed from the input (xA , xB , xC ) and let t be the transcript of
the protocol that produces z. Then, for sufficiently large n, with probability 1 − O(ǫ),
C(z | t) ≤ C(xA , xB , xC ) − CO(xA , xB , xC ) + O(log

n
),
ǫ

where the constants in the O(·) notation depend on the universal machine, but not on (xA , xB , xC ).
Proof We fix a triplet of n-bit input strings (xA , xB , xC ) and we consider some randomness r = (rA , rB , rC ),
on which the protocol produces a string z which satisfies the relations (23) and (24). Recall that the set
of such r’s has probability 1 − ǫ. We have
C(xA , xB , xC | r) =+
=+
+

C(t, z, xA , xB , xC | r)
C(t1 | r) + C(t2 | t1 , r) + C(t3 | t[1 : 2], r) + . . . + C(t3k | t[1 : 3k − 1], r)
C(z | t, r) + C(xA | z, t, r) + C(xB | xA , z, t, r) + C(xC | xA , xB , z, t, r).

(42)

The first line follows because t and z are computed from xA , xB , xC and r, and the second line uses the
chain rule. Next, we break the sum in the right hand side of equation (42) into the sum q1 (r)+q2 (r)+q3 (r),
where the terms in the latter sum are defined as
q1 (r)

= C(t1 | r) + C(t4 | t[1 : 3], r) + . . . + C(t3k−2 | t[1 : 3k − 3], r) + C(xA | z, t, r)

q2 (r)

= C(t2 | t1 , r) + C(t5 | t[1 : 4], r) + . . . + C(t3k−1 | t[1 : 3k − 2], r) + C(xB | xA , z, t, r),

= C(t3 | t[1 : 2], r) + C(t6 | t[1 : 5], r) + . . . + C(t3k | t[1 : 3k − 1], r) + C(xC | xA , xB , z, t, r).
(43)
The following claim shows that q1 (r), q2 (r) and q3 (r) satisfy relations similar to those that define S(xA , xB , xC ).
q3 (r)

35

Claim B.2
(1) q1 (r) ≥+ C(xA | xB , xC , r), q2 (r) ≥+ C(xB | xA , xC , r), q3 (r) ≥+ C(xC | xA , xB , r).
(2) q1 (r) + q2 (r) ≥+ C(xA , xB | xC , r), q1 (r) + q3 (r) ≥+ C(xA , xC | xB , r), q2 (r) + q3 (r) ≥+ C(xB , xC |
xA , r).
Proof (of Claim B.2.) We show the first relation in (1).
C(xA | xB , xC , r) =+
=+
+
+
+

C(t, z, xA | xB , xC , r)
C(t1 | xB , xC , r) + C(t2 | t1 , xB , xC , r) + C(t3 | t[1 : 2], xB , xC , r)
C(t4 | t[1 : 3], xB , xC , r) + C(t5 | t[1 : 4], xB , xC , r) + C(t6 | t[1 : 5], xB , xC , r)
..
.
C(t3k−2 | t[1 : 3k − 3], xB , xC , r) + C(t3k−1 | t[1 : 3k − 2], xB , xC , r)
+C(t3k | t[1 : 3k − 1], xB , xC , r)
C(z | t, xB , xC , r) + C(xA | t, z, xB , xC , r).

(44)
The first line follows from the fact that t and z are computed from xA , xB , xC and r, and the second line
follows from the chain rule.
For every ℓ ∈ {1, . . . , k}, C(t3ℓ−1 | t[1 : 3ℓ − 2], xB , xC , r) =+ 0, because t3ℓ−1 is computed from
t[1 : 3ℓ−2], xB , xC , r). For the same reason, C(t3ℓ | t[1 : 3ℓ−1], xB , xC , r) =+ 0 and C(z | t, xB , xC , r) =+ 0.
Eliminating the terms that are =+ 0 in equation (44) and also the conditioning on xB and xC in all terms
on the right hand side, we obtain
≤+ C(t1 | r) + C(t4 | t[1 : 3], r) + . . . + C(t3k−2 | t[1 : 3k − 3], r) + C(xA | z, t, r)
= q1 (r).
(45)
The other relations in the claim are proved in a similar way.
(End of proof of Claim B.2).
Combining relation (42) and the relations in Claim B.2, we obtain that with probability 1 − ǫ (over the
choice of r),
C(xA , xB , xC | r) ≥+ C(z | t, r) + (q1 (r) + q2 (r) + q3 (r)).
C(xA | xB , xC , r)

The next observation is that in the above equation we can drop the conditioning on the randomness r, if
we exclude an event that has probability ǫ. Indeed, if ǫ > 0 is an arbitrary constant and u is an arbitrary
string, which is sufficiently long, then C(u | r) =+ C(u) with probability of r at least 1 − ǫ, where r is
uniformly distributed over the set of binary strings of some length that depends on u.
In this way, we obtain that with probability 1 − ǫ, there is a tuple (q1 , q2 , q3 ) ∈ S(xA , xB , xC ) such that
C(z | t) ≤+ C(xA , xB , xC ) − (q1 + q2 + q3 ),
Since q1 + q2 + q3 ≥ CO(xA , xB , xc), we obtain the desired conclusion.

36

