# Secret Key Agreement¶

One of the only methods of encrypting a message from Alice to Bomb such that no third party (Eve) can possibly decrypt it is a one-time pad. This technique requires that Alice and Bob have a secret sequence of bits, $$S$$, which Alice then encrypts by computing the exclusive-or of it with the plaintext, $$P$$, to produce the cyphertext, $$C$$: $$C = S \oplus P$$. Bob can then decrypt by xoring again: $$P = S \oplus C$$.

In order to pull this off, Alice and Bob need to construct $$S$$ out of some sort joint randomness, $$p(x, y, z)$$, and public communication, $$V$$, which is assumed to have perfect fidelity. The maximum rate at which $$S$$ can be constructed in the secret key agreement rate.

## Background¶

Given $$N$$ IID copies of a joint distribution governed by $$p(x, y, z)$$, let $$X^N$$ denote the random variables observed by Alice, $$Y^N$$ denote the random variables observed by Bob, and $$Z^N$$ denote the random variables observed by Even. A secret key agreement scheme consists of functions $$f$$ and $$g$$, as well as a protocol for public communication (producing $$V$$), and is considered $$R$$-achievable if:

$\begin{split}S_X = f(X^N, V) \\ S_Y = g(Y^N, V) \\ p(S_X = S_Y = S) \geq 1 - \epsilon \\ \I{S : V Z^N} \leq \epsilon \\ \frac{1}{N} \H{S} \geq R - \epsilon\end{split}$

The maximum rate $$R$$ such that there exists a $$R$$-achievable scheme is known as the secret key agreement rate. Intuitively, this means there exists some procedure such that, for every $$N$$ observations, Alice and Bob can publicly converse and then construct $$S$$ bits which agree almost surely, and are almost surely independent of everything Eve has access to. $$S$$ is then known as a secret key.

There are three general classes of secret key agreement rates, depending on which parties are permitted to communicate. We discuss them below.

## No Communication¶

In the case that neither Alice nor Bob are permitted communication, the no-communication secret key agreement rate is given by:

$\operatorname{S}[X : Y || Z] = \I{X \meet Y | Z}$

where $$X \meet Y$$ is the Gács-Körner Common Information variable.

### Secrecy Capacity¶

Consider the situation that no party is allowed to communication, but rather than passively observing $$p(X, Y, Z)$$ Alice has full access to driving the channel $$p(Y, Z | X)$$. In this case we arrive at a maximum secret-key agreement rate known as the secrecy capacity, which is given by:

$\operatorname{S_C}[X \rightarrow Y || Z] = \displaystyle \max_{U - X - YZ} \I{U : Y} - \I{U : Z}$

## One-Way Communication¶

If only Alice is allowed to publicly broadcast information, the secret key agreement rate is given by:

$\operatorname{S}[X \rightarrow Y || Z] = \displaystyle \max_{V - U - X - YZ} \I{U : Y | V} - \I{U : Z | V}$

## Two-Way Communication¶

When both Alice and Bob are permitted communication, the secret key agreement rate, $$\operatorname{S}[X \leftrightarrow Y || Z]$$, is much more difficult to compute, and in fact only upper and lower bounds on this rate are known.

### Lower Bounds¶

The first few lower bounds on two-way secret key agreement rate are simply symmetrized forms of the more restricted secret key agreement rates.

#### Lower Intrinsic Mutual Information¶

The first lower bound on the secret key agreement rate is known in dit as the lower_intrinsic_mutual_information(), and is given by:

$\begin{split}\I{X : Y \uparrow Z} = \max \begin{cases} \I{X : Y} - \I{X : Z} \\ \I{X : Y} - \I{Y : Z} \\ 0 \end{cases}\end{split}$

#### Secrecy Capacity¶

Next is the secrecy capacity:

$\begin{split}\I{X : Y \uparrow\uparrow Z} = \max \begin{cases} \displaystyle \max_{U - X - YZ} \I{U : Y} - \I{U : Z} \\ \displaystyle \max_{U - Y - XZ} \I{U : X} - \I{U : Z} \end{cases}\end{split}$

This gives the secret key agreement rate when communication is not allowed.

#### Necessary Intrinsic Mutual Information¶

A tighter bound is given by the necessary_intrinsic_mutual_information() [GGunluK17], which is the maximum of the two one-way secret key agreement rates:

$\begin{split}\I{X : Y \uparrow\uparrow\uparrow Z} = \max \begin{cases} \displaystyle \max_{V - U - X - YZ} \I{U : Y | V} - \I{U : Z | V} \\ \displaystyle \max_{V - U - Y - XZ} \I{U : X | V} - \I{U : Z | V} \end{cases}\end{split}$

#### Interactive Intrinsic Mutual Information¶

$\begin{split}\I{X : Y \uparrow\uparrow\uparrow\uparrow Z} = \max \sum_{i \textrm{even}} \I{U_i : Y | U_{0 \ldots i}} - \I{U_i : Z | U_{0 \ldots i}} + \\ \sum_{i \textrm{odd}} \I{U_i : X | U_{0 \ldots i}} - \I{U_i : Z | U_{0 \ldots i}}\end{split}$

### Upper Bounds¶

#### Upper Intrinsic Mutual Information¶

The secret key agreement rate is trivially upper bounded by:

$\min\{ \I{X : Y}, \I{X : Y | Z} \}$

Intrinsic Mutual Information *****************&******

The intrinsic_mutual_information() [MW97] is defined as:

$\I{X : Y \downarrow Z} = \min_{p(\overline{z} | z)} \I{X : Y | \overline{Z}}$

It is straightforward to see that $$p(\overline{z} | z)$$ being a constant achieves $$\I{X : Y}$$, and $$p(\overline{z} | z)$$ being the identity achieves $$\I{X : Y | Z}$$.

#### Reduced Intrinsic Mutual Information¶

This bound can be improved, producing the reduced_intrinsic_mutual_information() [RSW03]:

$\I{X : Y \downarrow\downarrow Z} = \min_{U} \I{X : Y \downarrow ZU} + \H{U}$

This bound improves upon the Intrinsic Mutual Information when a small amount of information, $$U$$, can result in a larger decrease in the amount of information shared between $$X$$ and $$Y$$ given $$Z$$ and $$U$$.

#### Minimal Intrinsic Mutual Information¶

The Reduced Intrinsic Mutual Information can be further reduced into the minimal_intrinsic_total_correlation() [GA17]:

$\I{X : Y \downarrow\downarrow\downarrow Z} = \min_{U} \I{X : Y | U} + \I{XY : U | Z}$

#### Two-Part Intrinsic Mutual Information¶

$\I{X : Y \downarrow\downarrow\downarrow\downarrow Z} = inf_{J} min_{V - U - XY - ZJ} \I{X : Y | J} + \I{U : J | V} - \I{U : Z | V}$

### All Together Now¶

Taken together, we see the following structure:

\begin{split}\begin{align} &\min\{ \I{X : Y}, \I{X : Y | Z} \} \\ &\quad \geq \I{X : Y \downarrow Z} \\ &\quad\quad \geq \I{X : Y \downarrow\downarrow Z} \\ &\quad\quad\quad \geq \I{X : Y \downarrow\downarrow\downarrow Z} \\ &\quad\quad\quad\quad \geq \I{X : Y \downarrow\downarrow\downarrow\downarrow Z} \\ &\quad\quad\quad\quad\quad \geq S[X \leftrightarrow Y || Z] \\ &\quad\quad\quad\quad\quad\quad \geq \I{X : Y \uparrow\uparrow\uparrow\uparrow Z} \\ &\quad\quad\quad\quad\quad\quad\quad \geq \I{X : Y \uparrow\uparrow\uparrow Z} \\ &\quad\quad\quad\quad\quad\quad\quad\quad \geq \I{X : Y \uparrow\uparrow Z} \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad \geq \I{X : Y \uparrow Z} \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \geq S[X : Y || Z] \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \geq 0.0 \end{align}\end{split}

### Generalizations¶

Most of the above bounds have straightforward multivariate generalizations. These are not necessarily bounds on the multiparty secret key agreement rate. For example, one could compute the minimal_intrinsic_dual_total_correlation():

$\B{X_0 : \ldots : X_n \downarrow\downarrow\downarrow Z} = \min_{U} \B{X_0 : \ldots : X_n | U} + \I{X_0, \ldots, X_n : U | Z}$

### Examples¶

Let us consider a few examples:

In [1]: In [1]: from dit.multivariate.secret_key_agreement import *


First, we consider the distribution intrinsic_1:

In [2]: In [3]: print(intrinsic_1)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
----> 1 print(intrinsic_1)

NameError: name 'intrinsic_1' is not defined

In [3]: Class:          Distribution

In [4]: Alphabet:       ('0', '1', '2', '3') for all rvs
...: Base:           linear
...: Outcome Class:  str
...: Outcome Length: 3
...: RV Names:       None
...:
File "<ipython-input-4-f997bcd614eb>", line 1
Alphabet:       ('0', '1', '2', '3') for all rvs
^
SyntaxError: invalid syntax


With upper bounds:

In [5]: In [4]: upper_intrinsic_mutual_information(intrinsic_1, [[0], [1]], [2])
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
----> 1 upper_intrinsic_mutual_information(intrinsic_1, [[0], [1]], [2])

NameError: name 'intrinsic_1' is not defined

In [6]: Out[4]: 0.5


We see that the trivial upper bound is 0.5, because without conditioning on $$Z$$, $$X$$ and $$Y$$ can agree when the observe either a $$2$$ or a $$3$$, which results in $$\I{X : Y} = 0.5$$. Given $$Z$$, however, that information is no longer private. But, given $$Z$$, a conditional dependence is induced between $$X$$ and $$Y$$: $$Z$$ knows that if she is a $$0$$ that $$X$$ and $$Y$$ agree, and if she is a $$1$$ they disagree. This results $$\I{X : Y | Z} = 0.5$$. In either case, however, $$X$$ and $$Y$$ can not agree upon a secret key: in the first case the eavesdropper knows their correlation, while in the second they are actually independent.

The intrinsic_mutual_information(), however can detect this:

In [7]: In [5]: intrinsic_mutual_information(intrinsic_1, [[0], [1]], [2])
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-7-cf75a74ddcab> in <module>
----> 1 intrinsic_mutual_information(intrinsic_1, [[0], [1]], [2])

NameError: name 'intrinsic_1' is not defined

In [8]: Out[5]: 0.0


Next, let’s consider the distribution intrinsic_2:

In [9]: In [7]: print(intrinsic_2)
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-9-094f23e395aa> in <module>
----> 1 print(intrinsic_2)

NameError: name 'intrinsic_2' is not defined

In [10]: Class:          Distribution

In [11]: Alphabet:       (('0', '1', '2', '3'), ('0', '1', '2', '3'), ('0', '1'))

In [12]: Base:           linear
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-12-822bc640d06e> in <module>
----> 1 Base:           linear

NameError: name 'linear' is not defined

In [13]: Outcome Class:  str
....: Outcome Length: 3
....: RV Names:       None
....:
File "<ipython-input-13-ab3546a5787a>", line 1
Outcome Class:  str
^
SyntaxError: invalid syntax


In this case, $$Z$$ no longer can distinguish between the case where $$X$$ and $$Y$$ can agree on a secret bit, and when they can not, because she can not determine when they are in the $$01$$ regime or in the $$23$$ regime:

In [14]: In [8]: intrinsic_mutual_information(intrinsic_2, [[0], [1]], [2])
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-14-066b11243fe9> in <module>
----> 1 intrinsic_mutual_information(intrinsic_2, [[0], [1]], [2])

NameError: name 'intrinsic_2' is not defined

In [15]: Out[8]: 1.5


This seems to imply that $$X$$ and $$Y$$ can adopt a scheme such as: if they observe either a $$0$$ or a $$1$$, write down $$0$$, and if they observe either a $$2$$ or a $$3$$, write that down. This has a weakness, however: what if $$Z$$ were able to distinguish the two regimes? This costs her $$1$$ bit, but reduces the secrecy of $$X$$ and $$Y$$ to nil. Thus, the secret key agreement rate is actually only $$1$$ bit:

In [16]: In [9]: minimal_intrinsic_mutual_information(intrinsic_2, [[0], [1]], [2], bounds=(3,))
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-16-523cc5b9b003> in <module>
----> 1 minimal_intrinsic_mutual_information(intrinsic_2, [[0], [1]], [2], bounds=(3,))

NameError: name 'intrinsic_2' is not defined

In [17]: Out[9]: 1.0