Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings

To prove our main result, we propose an explicit construction of a tuple that provides the negative answer to Question 2. This construction is based on incidences in a finite projective plane. We fix a finite field $𝔽$, take the projective plane over this field, and consider pairs $(x,y)$, where $x$ is a line in this plane and $y$ is a projective line passing through a point. We call such pairs incidences. An incidence in a projective plane is a classical combinatorial object, and its properties were extensively studied in different contexts. Incidences were considered in AIT, see, e.g., [17, 5].

In a projective plane over $𝔽$ there are $\mathrm{\Theta }({|𝔽|}^2)$ points, $\mathrm{\Theta }({|𝔽|}^2)$ lines, and $\mathrm{\Theta }({|𝔽|}^3)$ incidences. For the vast majority of incidences $(x,y)$ we have

The upper bounds are trivial: to specify a point or a line in a projective plane, it is enough to provide two elements of $𝔽$; to specify together a point and a line incident to this point, it is enough to provide three elements of $𝔽$. The lower bound follows from a simple counting argument: the number of programs (descriptions) shorter than $k$ is less than $2^k$; therefore, for most incidences $(x,y)$ there is no short description, and $C(x,y)\approx 3\log |𝔽|$. A similar argument implies $C(x)\approx 2\log |𝔽|$ and $C(y)\approx 2\log |𝔽|$. We call an incidence $(x,y)$ typical if it satisfies (1).

Thus, for a typical incidence $(x,y)$ the mutual information between $x$ and $y$ is

An. Muchnik observed in [17] that the mutual information of an incidence is hard to “materialize,” i.e., we cannot find a $z$ that “embodies” this amount of information shared by $x$ and $y$. More formally, Muchnik proved that

This insight did not close the question completely: the optimal trade-off between $C(z\mid x)$, $C(z\mid y)$, $C(z)$ is still not fully understood. Our work follows this direction of research. We prove that for prime fields $𝔽$, some specific values of $C(z\mid x)$, $C(z\mid x)$, and $C(z)$ are forbidden:

see a more precise statement in Theorem 3.8 on p. 3.8. This result contrasts with a much simpler fact proven in [19]:

see Theorem 3.7 on p. 3.7.

Our proof of (2) uses a remarkable result by Sophie Stevens and Frank De Zeeuw, which gives a non-trivial upper bound on the number of incidences between points and lines in a plane over a prime field [26]. The first theorem of this type was proven by Bourgain, Katz, and Tao, [2]. This result has been improved further in [10, 11, 12]. We use the bound from [26], the strongest to date.

Typical incidences in the projective plane over a prime field imply the negative answer to Question 2: if $(x,y)$ is a typical incidence, we let

and prove that for every string $z$ satisfying the conditions $C(a\mid z)\approx \frac{1}{2}C(a)\text{ and }C(b\mid z)\approx \frac{1}{2}C(b),$ the value of $C(c\mid z)$ must be much smaller than $\frac{1}{2}C(c)$, see Corollary 3.9.

The main result (2) can be interpreted as a partial (very limited in scope) answer to Question 3, as it claims that for some specific pairs $(x,y)$ (typical incidences) there exist limitations for realizable complexity profiles of triples $(x,y,z)$. It is no surprise that this fact can be used to prove certain no-go results in communication complexity, for settings where the participants of the protocol are given such $x$ and $y$ as their inputs. We present an example of such result – a theorem on secret key agreement protocols, as we explain below.

Unconditional secret key agreement is one of the basic primitive in information-theoretic cryptography, [27]. In the simplest setting, this is a protocol for two parties, Alice and Bob. At the beginning of the communication, Alice and Bob are given some input data, $x$ and $y$ respectively. It is assumed that $x$ and $y$ are strongly correlated, i.e., the mutual information between $x$ and $y$ is non-negligible. Further, Alice and Bob exchange messages over a public channel and obtain (on both sides) some string $w$ that is incompressible (i.e., $C(w)$ is close to its length) and has negligible mutual information with the transcript of the protocol, i.e.,

Thus, Alice and Bob transform the mutual information between $x$ and $y$ into a common secret key (which can later be used, for example, into a one-time-pad or some other unconditionally secure cryptographic scheme). The secrecy of the key means that an eavesdropper should get (virtually) no information about this key, even having intercepted all communication between Alice and Bob. For a more detailed discussion of the secret key agreement in the framework of AIT we refer the reader to [21, 8].

The challenges in secret key agreement are to (i) maximize the size of the secret key and (ii) to minimize the communication complexity of the protocol (the total length of messages sent to each other by Alice and Bob). It is known that the maximum size of the secret key is equal to the mutual information between $x$ and $y$, i.e., $I(x:y)=C(x)+C(y)-C(x,y)$ (see [21] for the proof in the framework of AIT and [1, 16] for the original result in the classical Shannon’s settings). There exists a communication protocol that allows to produce a secret of optimal size with communication complexity

see [21], and this communication complexity is tight, at least for some “hard” pairs of inputs $(x,y)$, see [8]. Moreover, subtler facts are known:

• $\mathrm{■}$

  the standard protocol achieving (4) (the construction dates back to [1, 16]; see [21] for the AIT version) is highly asymmetric: all messages are sent by only one party (Alice or Bob);

• $\mathrm{■}$

  for some pairs of inputs $(x,y)$, if we want to agree on a secret key of maximal possible size $I(x:y)$, not only the total communication complexity must be equal to (4), but actually one of the parties (Alice or Bob) must send $\max \{C(x\mid y),C(y\mid x)\}$ bits of information, [3];

• $\mathrm{■}$

  for some pairs of inputs $(x,y)$, the total communication complexity $\max \{C(x\mid y),C(y\mid x)\}$ cannot be reduced even if the parties need to agree on a sub-optimal secret key of size $\delta n$ (for any constant $\delta >0$), see [8].

It remains unknown whether we can always organize a protocol of secret key agreement where the communication complexity (4) is shared evenly by the parties (both Alice and Bob send $\frac{1}{2}C(x\mid y)$ bits) if they need to agree on a key of sub-optimal size, e.g., $\frac{1}{2}I(x:y)$.

When we claim that communication complexity of a protocol is large in the worst case, i.e., Alice and Bob must send to each other quite a lot of bits at least for some pairs of inputs, it is enough to prove this statement of some specific pair of data sets $(x,y)$. Such a proof may become simpler when we use $(x,y)$ with nice combinatorial properties, even though these inputs may look artificial and unusual for practical applications. Such is the case with the mentioned lower bounds for communication complexity proven in [8] and [3]. Both these arguments employ as an instance of a “hard” input $(x,y)$ a typical incidence in a finite projective plane. Thus, it is natural to ask whether, for these specific $(x,y)$, it is possible to agree on a secret key of sub-optimal size using a balanced communication load – that is, when Alice and Bob each send approximately the same number of bits, roughly half the total communication complexity. We show, quite surprisingly, that the answer to this question depends on whether the field admits a proper subfield:

For a more precise statements see Theorem 4.3 and Theorem 4.1 respectively.

A projective plane is a classical geometric object, and combinatorial properties of discrete projective planes have been studied with a large variety of mathematical techniques. It is no surprise that, in the context of AIT, the information-theoretic properties of incidences in discrete projective planes have been studied using many different mathematical tools. In this paper we bring to AIT another (rather recent) mathematical technique that helps distinguish information-theoretic properties of projective planes over prime fields and over fields containing proper subfields.

As we mentioned above, we apply the new approach to the problem of secret key agreement: we consider the setting where Alice and Bob receive as inputs data sets $x$ and $y$ such that $(x,y)$ is a “typical” incidence in a projective plane ($x$ is a line and $y$ is a point incident to this line) over a finite field $𝔽$ with $n=\lceil \log |𝔽|\rceil$. We summarize in Table 1 below several technical results concerning this communication problem, and the techniques in the core of these results.

One of the motivations for writing this paper was to promote the notable results of [2, 10, 11, 12, 26], which presumably can find interesting applications in AIT and communication complexity.

The rest of the paper is structured as follows. In Section 2 we briefly discuss (3) (known from [19]). In Section 3 we formally prove our main result (2). In Section 4 we discuss an application of the main result: we show that the performance of the secret key agreement for Alice and Bob given as inputs an incident pair $(x,y)$ (from a projective plane) differs between fields that do and do not contain proper subfields.

• $\mathrm{■}$

  $|𝒮|$ stands for the cardinality of a finite set $𝒮$

• $\mathrm{■}$

  we write $F(n)\ll G(n)$ if $G(n)-F(n)=\mathrm{\Omega }(n)$ (e.g., $\frac{22n}{15}\ll \frac{3n}{2}$)

• $\mathrm{■}$

  for a bit string $x$ we denote by $x_{k:m}$ a factor of $x$ that consists of $m-k+1$ bits at the positions between $k$ and $m$ (in particular, $x_{[1:m]}$ is a prefix of $x$ of length $m$);

• $\mathrm{■}$

  we denote $𝔽\mathbb{P}$ the projective plane over a finite field $𝔽$;

• $\mathrm{■}$

  $G=(R,L;E)$ stands for a bipartite graph where $L\cup R$ (disjoint union) is the set of vertices and $E\subset L\times R$ is the set of edges;

• $\mathrm{■}$

  $C(x)$ and $C(x\mid y)$ stand for Kolmogorov complexity of a string $x$ and, respectively, conditional Kolmogorov complexity of $x$ conditional on $y$, see [14, 22]. We use a similar notation for more involved expressions, e.g., $C(x,y\mid v,w)$ denotes Kolmogorov complexity of the code of the pair $(x,y)$ conditional on the code of another pair $(v,w)$

• $\mathrm{■}$

  we also talk about Kolmogorov complexity of more complex combinatorial objects (elements of finite fields, graphs, points and lines in a discrete projective plane, and so on) assuming that each combinatorial object is represented by its code (for some fixed computable encoding rule)

• $\mathrm{■}$

  $I(x:y):=C(x)+C(y)-C(x,y)$ and $I(x:y\mid z):=C(x\mid z)+C(y\mid z)-C(x,y\mid z)$ stand for information in $x$ on $y$ and, respectively, information in $x$ on $y$ conditional on $z$

Many natural equalities and inequalities for Kolmogorov complexity are valid only up to a logarithmic additive term, e.g., $C(x,y)=C(x)+C(y\mid x)\pm O(\log n),$ where $n$ is the sum of lengths of $x$ and $y$ (this is the chain rule a.k.a. Kolmogorov–Levin theorem, see [30]). To simplify the notation, we write $A\stackrel{\log }{\le }B$ instead of $A\le B+O(\log N),$ where $N$ is the sum of lengths of all strings involved in the expressions $A$ and $B$. Similarly we define $A\stackrel{\log }{\ge }B$ (which means $B\stackrel{\log }{\le }A$) and $A\stackrel{\log }{=}B$ (which means $A\stackrel{\log }{\le }B$ and $B\stackrel{\log }{\le }A$). For example, the chain rule can be expressed as

the well known fact of symmetry of the mutual information can be expressed as

In this section we introduce the framework that helps to translated information-theoretic questions in the combinatorial language.

Now we instantiate the framework discussed above and discuss the central construction of this paper – typical incidences in a finite projective plane.

We proceed with a discussion of properties of $(x,y)$ from Example 3.6 that differ depending on whether $𝔽$ possesses a proper subfield.

Let us focus on the case where the inputs $(x,y)$ represent a pair of typical incidences in a projective plane over a finite field $𝔽$ (we denote $n:=\lceil \log |𝔽|\rceil$). In this case the upper bound (4) (which rewrites in this case to to $n$) is tight, the communication complexity cannot be made better than $n-O(\log n)$, [8]. Moreover,

1. (i)

   for every communication protocol, for its transcript $t$ we have

   $$C(t)\stackrel{\log }{\ge }I(t:x\mid y)+I(t:y\mid x)\stackrel{\log }{\ge }n,$$

   (the first inequality is known from [21] and the second one from [8]);

2. (ii)

   this bound remains valid even if the parties agree on a sub-optimal secret key of size $\delta n$ for any $\delta >0$,[8];

3. (iii)

   if Alice and Bob agree on a secret key $w$ of maximal possible size $I(x:y)=n$, then not only the total communication complexity must be equal to $n$ but actually one of the parties (Alice or Bob) must send $\max \{C(x\mid y),C(y\mid x)\}\stackrel{\log }{=}n$ bits of information, [3].

We summarize:

• $\mathrm{■}$

  even for a suboptimal key size communication complexity of the protocol $\stackrel{\log }{\ge }n$;

• $\mathrm{■}$

  for an optimal key size the communication is very asymmetric – all $n$ bits are sent by one of the participants.

There remained a question: Does there exist a protocol with a symmetric communication load (both Alice and Bob send $\approx n/2$ bits) with a suboptimal key size? In what follows we show that the answer to this question depends on whether the underlying field contains a proper subfield.