Secret Key Agreement

One of the only methods of encrypting a message from Alice to Bob 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 Eve. 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}\]

[ACsiszar93]. It suffices to take \(|V| \leq |X|\) and \(|U| \leq |X|^2\) [EGK11]: \(V\) splits Alice’s distribution into at most \(|X|\) parts, and \(U\) splits each of those into at most \(|X|\) further parts.

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}\]

Iterated Public Discarding

The iterated_discarding_skar() restricts the interactive bound to protocols in which every auxiliary variable is a public keep/discard flag [Mau93]. Alice and Bob alternate rounds; in each round the speaker announces, independently for each position, whether to keep it, with a keep probability \(k_i(\cdot)\) that depends only on their own symbol. Discarded positions are abandoned, and on the surviving positions whichever party fares better sends their variable as a one-way key, yielding the final term \(\max\{\I{X : Y} - \I{X : Z}, \I{X : Y} - \I{Y : Z}\}\) evaluated on the post-selected distribution. Each round contributes \(\I{U_i : Y} - \I{U_i : Z}\) (Alice speaking) or \(\I{U_i : X} - \I{U_i : Z}\) (Bob speaking), weighted by the probability that a position survives the earlier rounds.

Because each round needs only one keep probability per symbol, this bound remains tractable for many more rounds than interactive_intrinsic_mutual_information(). For example, the W distribution, \(\{100, 010, 001\}\) uniformly, has a one-way secret key agreement rate of zero in both directions, while iterated discarding reaches approximately \(0.138\), \(0.164\), and \(0.174\) bits with one, two, and three discarding rounds, approaching roughly \(0.186\) bits as the number of rounds grows.

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}\). dit uses both corruptions as seeds of the basin-hopping search, so the minima it considers always include these two values.

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\).

Although written as a nested minimization, the inner intrinsic mutual information is itself a minimization over \(p(\overline{z} | z u)\), and \(\H{U}\) does not depend on \(\overline{Z}\). The two minimizations therefore combine into a single joint minimization over two chained channels, \(p(u | x y z)\) and \(p(\overline{z} | z u)\):

\[\I{X : Y \downarrow\downarrow Z} = \min_{p(u | x y z),\, p(\overline{z} | z u)} \I{X : Y | \overline{Z}} + \H{U}\]

This is how dit computes it, with \(|\overline{Z}| \leq |Z| |U|\) from the corresponding bound for the intrinsic mutual information [RSW03].

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

The two_part_intrinsic_mutual_information() [GA17, GA10] is:

\[\I{X : Y \downarrow\downarrow\downarrow\downarrow Z} = \inf_{J} \max_{V - U - XY - ZJ} \I{X : Y | J} + \I{U : J | V} - \I{U : Z | V}\]

The inner maximization is the one-way secret key agreement rate from \(XY\) to \(J\) with \(Z\) eavesdropping. No cardinality bound on \(J\) is known, so the bound cannot be computed exactly [GA17]; any particular \(J\) still yields a valid upper bound, provided the inner maximization is solved exactly.

Relaxed Two-Part Intrinsic Mutual Information

Because the inner maximization above is a one-way secret key agreement rate, it is bounded from above by the Intrinsic Mutual Information \(\I{XY : J \downarrow Z}\) [MW97]. Substituting this gives the relaxed_two_part_intrinsic_mutual_information():

\[\I{X : Y \downarrow\downarrow\downarrow\downarrow_r Z} = \min_{p(j | x y z),\, p(\overline{z} | z)} \I{X : Y | J} + \I{XY : J | \overline{Z}}\]

Since \(\I{XY : J \downarrow Z} \leq \I{XY : J | Z}\), it is never larger than the Minimal Intrinsic Mutual Information, and since it relaxes only the inner maximization, it is never smaller than the two-part intrinsic mutual information. Unlike the latter, it is a single joint minimization over two channels, with \(|\overline{Z}| \leq |Z|\) [CRW03]. Restricting the size of \(J\) or stopping at a local optimum can therefore only loosen it, never invalidate it, which is why two_way_skar() uses it in place of the two-part bound.

Less-Noisy Intrinsic Mutual Information

If Eve’s channel \(p(z | x y)\) is less noisy than a channel \(p(j | x y)\), meaning \(\I{U : Z} \geq \I{U : J}\) for every \(U - XY - ZJ\) and every input distribution, then no protocol can distill more key against \(Z\) than against \(J\) [GGunluK17]. The less_noisy_intrinsic_mutual_information() [PGR26] optimizes over all such \(J\):

\[\I{X : Y \downarrow_{\mathrm{ln}} Z} = \inf_{p(j | x y) \,:\, p(z | x y) \succeq_{\mathrm{ln}} p(j | x y)} \I{X : Y | J}\]

Every degradation \(p(\overline{z} | z)\) is dominated, so this never exceeds the Intrinsic Mutual Information, and it is never smaller than the inf-max upper bound of Gohari and Anantharam (2010), stated as Eq. (11) of [AG26]. It is not comparable in general to the reduced or minimal intrinsic mutual informations.

A channel is less noisy than another iff the difference of the two output entropies is concave in the input distribution [vD97]. That forces every dominated channel to factor as \(p(j | x y) = \sum_z p(z | x y) K(z, j)\) for a real, possibly signed, matrix \(K\); dit optimizes over \(K\), imposing the concavity condition on a finite sample of input distributions.

The distribution bound_information of [PGR26] has \(\I{X : Y \downarrow Z} > 0\) but \(\I{X : Y \downarrow_{\mathrm{ln}} Z} = 0\), and so a secret key agreement rate of zero. When \(X\) and \(Y\) are binary and \(Z = X \oplus Y\), every known upper bound, this one included, equals \(\I{X : Y}\) [AG26].

All Together Now

Taken together, we see the following structure:

\[\begin{split}\begin{aligned} &\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_r 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 \max\{ \I{X : Y \uparrow Z}, S[X : Y || Z] \} \\ &\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \geq 0.0 \end{aligned}\end{split}\]

The secrecy capacity dominates both of the final two bounds: choosing \(U = X\) (or \(U = Y\)) recovers \(\I{X : Y \uparrow Z}\), and choosing \(U = X \meet Y\) recovers \(S[X : Y || Z]\). The final two bounds, however, are incomparable. For example, let \(W\), \(A\), and \(B\) be independent uniform bits, and let \(X = (W, A)\), \(Y = (W, B)\), and \(Z = (A, B)\). Then \(S[X : Y || Z] = \H{W | Z} = 1\) bit, since Alice and Bob share \(W\) and Eve knows nothing about it, while \(\I{X : Y} = \I{X : Z} = \I{Y : Z} = 1\) bit, so \(\I{X : Y \uparrow Z} = 0\).

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]: from dit.multivariate.secret_key_agreement import *

In [2]: from dit.example_dists.intrinsic import intrinsic_1, intrinsic_2, intrinsic_3

First, we consider the distribution intrinsic_1:

In [3]: print(intrinsic_1)
Class:    Distribution
Alphabet: (('0', '1', '2', '3'), ('0', '1', '2', '3'), ('0', '1', '2', '3'))
Base:     linear

x                 p(X0,X1,X2)
('0', '0', '0')   1/8
('0', '1', '1')   1/8
('1', '0', '1')   1/8
('1', '1', '0')   1/8
('2', '2', '2')   1/4
('3', '3', '3')   1/4

With upper bounds:

In [4]: upper_intrinsic_mutual_information(intrinsic_1, [[0], [1]], [2])
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 [5]: intrinsic_mutual_information(intrinsic_1, [[0], [1]], [2])
Out[5]: 0.0

Next, let’s consider the distribution intrinsic_2:

In [6]: print(intrinsic_2)
Class:    Distribution
Alphabet: (('0', '1', '2', '3'), ('0', '1', '2', '3'), ('0', '1'))
Base:     linear

x                 p(X0,X1,X2)
('0', '0', '0')   1/8
('0', '1', '1')   1/8
('1', '0', '1')   1/8
('1', '1', '0')   1/8
('2', '2', '0')   1/4
('3', '3', '1')   1/4

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 [7]: intrinsic_mutual_information(intrinsic_2, [[0], [1]], [2])
Out[7]: 1.4999999999999996

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 [8]: minimal_intrinsic_mutual_information(intrinsic_2, [[0], [1]], [2], bounds=(3,))
Out[8]: 1.0

Two further sources come from [AG26]. In the deterministic_erasure source, \(X\) is uniform on four symbols, Eve sees \(Z = \lfloor X / 2 \rfloor\), and Bob sees \(X\) through an erasure channel with erasure probability \(\epsilon\). Abin and Gohari show that one-way communication achieves the upper bound \(\I{X : Y | Z} = (1 - \epsilon) \H{X | Z}\). Because \(Z\) is a function of \(X\), \(Y - X - Z\) is a Markov chain, so this also follows from the trivial lower bound \(\I{X : Y} - \I{Y : Z} = \I{X : Y | Z}\) [Mau93]. Here it is with \(\epsilon = 0.3\):

In [9]: from dit.example_dists.intrinsic import deterministic_erasure_source, xor_key

In [10]: lower_intrinsic_mutual_information(deterministic_erasure_source, [[0], [1]], [2])
Out[10]: 0.7000000000000002

In [11]: intrinsic_mutual_information(deterministic_erasure_source, [[0], [1]], [2])
Out[11]: 0.7000000000000002

The xor_key source has binary \(X\) and \(Y\) with any joint distribution, and \(Z = X \oplus Y\). Every known upper bound equals \(\I{X : Y}\), and the true rate is open: Abin and Gohari conjecture that it is smaller for some distributions.

In [12]: d = xor_key([0.4, 0.1, 0.2, 0.3])

In [13]: upper_intrinsic_mutual_information(d, [[0], [1]], [2])
Out[13]: 0.12451124978365313

In [14]: intrinsic_mutual_information(d, [[0], [1]], [2])
Out[14]: 0.12451124978365313

Secret key agreement asks how much key can be extracted from \(p(x, y, z)\). The reverse question asks how much secret key Alice and Bob must consume to form \(p(x, y, z)\): starting from shared secret bits, they use local operations and public communication to produce \(X^N Y^N\), such that Eve could simulate the public transcript by processing \(Z^N\). The minimal rate is the secret_key_cost(), also called the information of formation [RW03]. Winter found a single-letter formula for it [CHW16, Win05]:

\[\begin{split}\operatorname{K_c}[X : Y || Z] = \min_{\substack{XY - Z - U \\ X - UV - Y}} \I{XY : V | U}\end{split}\]

with \(|U| \leq |Z| + 1\) and \(|V| \leq |X||Y|\). For each choice of \(U\) the inner minimization is the conditional Wyner common information \(\C{X : Y | U}\), so the secret key cost is a Wyner common information minimized over degradations of \(Z\), just as the Intrinsic Mutual Information minimizes the conditional mutual information. Since \(\C{X : Y | U} \geq \I{X : Y | U}\),

\[S[X \leftrightarrow Y || Z] \leq \I{X : Y \downarrow Z} \leq \operatorname{K_c}[X : Y || Z] \leq \min\{ \C{X : Y}, \C{X : Y | Z} \}\]

where the middle inequality is due to [RW03]. When \(Z\) is independent of \(XY\), the secret key cost is the Wyner common information \(\C{X : Y}\).

dit builds the second Markov chain into the parametrization, as it does for the Wyner common information: \(U\) is a channel from \(Z\), \(V\) a channel from \(XU\), and a copy \(Y'\) a channel from \(UV\), subject to \(XY'U\) being distributed as \(XYU\). As with all of these optimizations, the result is a local minimum, and so an upper bound on the secret key cost.

For intrinsic_2, \(\I{X : Y \downarrow Z} = \C{X : Y | Z} = 1.5\), so forming it costs 1.5 bits of secret key, while only 1 bit can be extracted from it. For bound_information [PGR26], no key can be extracted, but the intrinsic mutual information is positive, and so is the cost of forming it; dit finds roughly \(0.026\) bits.

Sources with Known Rates

Exact secret key agreement rates are known for only a few sources, and dit includes several as test cases, each with its secret_rate attribute set:

• chitambar_bob_speaks: the rate \(\I{X : Y | Z} = 1/3\) is achieved when Bob announces whether \(y \in \{0, 1\}\), but not by one-way communication from Alice [CFH15].

• chitambar_two_way: the rate \(\I{X : Y | Z} = 1/5\) needs both parties to announce whether their symbol lies in \(\{0, 1\}\); one-way communication in either direction falls short [CFH15].

• james_problem: the “Problem” distribution of [JEC19], with the rate \(1/2\) attained by one-way communication and matched by \(\I{X : Y}\).

• reversely_degraded(a, b, c, e): two independent components, one degraded toward Bob and one toward Alice, with rate \(\I{X : Y | Z}\); achieving it needs two-way communication [ACsiszar93].

• gisin_wolf(alpha): a standard-basis measurement of a family of qutrit states [GW00]. For \(2 \leq \alpha \leq 3\), a degradation of \(Z\) makes \(X\) and \(Y\) independent, so the rate is \(0\); outside that interval it is positive [PGR26] but unknown.

In [15]: from dit.example_dists.intrinsic import chitambar_two_way

In [16]: upper_intrinsic_mutual_information(chitambar_two_way, [[0], [1]], [2])
Out[16]: 0.20000000000000018

In [17]: chitambar_two_way.secret_rate
Out[17]: 0.2

Multiterminal Secret Key Capacity

When there is no eavesdropper side information but many terminals, the secret key capacity is known exactly [CsiszarN04]. Each terminal \(j \in \mathcal{M}\) observes \(X_j\), all of them may discuss publicly, and only the terminals in a key set \(\mathcal{A} \subseteq \mathcal{M}\) must end up with the key; the rest are helpers, from whom the key need not be hidden. The capacity is

\[C_{SK}^{\mathcal{A}} = \H{X_\mathcal{M}} - R_{CO}^{\mathcal{A}}\]

where \(R_{CO}^{\mathcal{A}}\) is the minimum rate of communication for omniscience, the least total public discussion after which every terminal in \(\mathcal{A}\) knows every \(X_j\):

\[R_{CO}^{\mathcal{A}} = \min \sum_{j \in \mathcal{M}} R_j \quad \text{s.t.} \quad \sum_{j \in \mathcal{B}} R_j \geq \H{X_\mathcal{B} | X_{\mathcal{B}^c}} \quad \forall\, \emptyset \neq \mathcal{B} \subsetneq \mathcal{M},\ \mathcal{A} \not\subseteq \mathcal{B}\]

dit solves this linear program directly, so the cost grows as \(2^{|\mathcal{M}|}\). If some terminals are compromised, revealing \(X_\mathcal{D}\) to the eavesdropper while still cooperating, the private key capacity is the same expression with every entropy conditioned on \(X_\mathcal{D}\); pass those variables as crvs. When \(\mathcal{A} = \mathcal{M}\), the capacity is the CAEKL Mutual Information.

Helpers can create key where none existed. If Alice and Bob hold independent uniform bits and a helper holds their xor, Alice and Bob alone share nothing, but after the helper announces its bit they share one secret bit:

In [18]: d = dit.Distribution(['000', '011', '101', '110'], [1/4] * 4)

In [19]: secret_key_capacity(d, [[0], [1], [2]], key_terminals=[0, 1])
Out[19]: 1.0

In [20]: omniscience_rate(d, [[0], [1], [2]], key_terminals=[0, 1])
Out[20]: 1.0

secret_key_capacity(dist, rvs=None, key_terminals=None, crvs=None)

Compute the multiterminal secret key capacity of Csiszár and Narayan [CsiszarN04].

The terminals in key_terminals (the set \(\mathcal{A}\)) agree on a secret key using unlimited public discussion; the remaining terminals act as helpers and need not be kept ignorant of the key. The capacity is

\[C_{SK}^{\mathcal{A}} = \H{X_\mathcal{M}} - R_{CO}^{\mathcal{A}},\]

where \(R_{CO}^{\mathcal{A}}\) is the omniscience_rate(). When crvs is given, every entropy is conditioned on it, which yields the private key capacity with those variables revealed to the eavesdropper. When every terminal is a key terminal this equals the caekl_mutual_information().

Parameters:

• dist (Distribution) – The distribution of interest.

• rvs (list, None) – A list of lists. Each inner list specifies the indexes of the random variables observed by one terminal. If None, each random variable is its own terminal.

• key_terminals (iterable of int, None) – Indices into rvs of the terminals that share the key. If None, all terminals share it.

• crvs (list, None) – Random variables known to the eavesdropper (e.g. those of compromised terminals, which still cooperate in the protocol).

Returns:

C_SK – The secret key capacity.

Return type:

float

Raises:

ditException – Raised if fewer than two key terminals are given, if key_terminals does not index into rvs, or if dist is symbolic.

Examples

A helper who knows the xor of Alice’s and Bob’s independent bits lets them agree on one secret bit:

>>> d = dit.Distribution(['000', '011', '101', '110'], [1 / 4] * 4)
>>> secret_key_capacity(d, [[0], [1], [2]], key_terminals=[0, 1])
1.0

omniscience_rate(dist, rvs=None, key_terminals=None, crvs=None)

Compute the minimum rate of public communication for omniscience [CsiszarN04].

This is the smallest total rate \(R_{CO}^{\mathcal{A}}\) of public discussion after which every terminal in the key set \(\mathcal{A}\) can recover the observations of all terminals \(\mathcal{M}\):

\[R_{CO}^{\mathcal{A}} = \min \sum_{j \in \mathcal{M}} R_j \quad \text{s.t.} \quad \sum_{j \in \mathcal{B}} R_j \geq \H{X_\mathcal{B} \mid X_{\mathcal{B}^c}} \quad \forall\, \emptyset \neq \mathcal{B} \subsetneq \mathcal{M},\ \mathcal{A} \not\subseteq \mathcal{B}.\]

Parameters:

• dist (Distribution) – The distribution of interest.

• rvs (list, None) – A list of lists. Each inner list specifies the indexes of the random variables observed by one terminal. If None, each random variable is its own terminal.

• key_terminals (iterable of int, None) – Indices into rvs of the terminals that must become omniscient. If None, all terminals must.

• crvs (list, None) – Random variables known to everyone, including the eavesdropper (e.g. those of compromised terminals); all entropies are conditioned on them.

Returns:

R_CO – The minimum communication rate for omniscience.

Return type:

float

Raises:

ditException – Raised if fewer than two key terminals are given, if key_terminals does not index into rvs, or if dist is symbolic.

Secret Key Cost