Definitions for The Sender-Excited Secret Key Agreement Model: Capacity, Reliability and Secrecy Exponents

QAlgorithms.Papers.Independent.Intakethird100.P76.AdmissibleCost

For a finite type $S$, a function $\mathrm{cost}:S\to\mathbb R$, and a real number $\Gamma$, this predicate means that $\Gamma>0$, there exists a real $L$ such that $0\le\mathrm{cost}(s)\le L$ for every $s\in S$, and there exists a function $p:S\to\mathbb R$ satisfying

$$p(s)\ge0\quad\text{for all }s,\qquad \sum_s p(s)=1,\qquad \sum_s p(s)\,\mathrm{cost}(s)\le\Gamma.$$

The expected-cost bound is non-strict, while positivity of $\Gamma$ is strict. If $S$ is empty, the normalization equation cannot hold, so the predicate is false.

QAlgorithms.Papers.Independent.Intakethird100.P76.Aux

For finite types $S,X$ and natural numbers $u,w$, an auxiliary datum consists of a function $p:S\to\mathbb R$ satisfying $p(s)\ge0$ and $\sum_s p(s)=1$, a function $q:(X\times S)\to\{0,\ldots,u-1\}\to\mathbb R$ satisfying $q(a\mid x,s)\ge0$ and $\sum_{a<u}q(a\mid x,s)=1$ for every $(x,s)$, and a function $r:\{0,\ldots,u-1\}\to\{0,\ldots,w-1\}\to\mathbb R$ satisfying $r(b\mid a)\ge0$ and $\sum_{b<w}r(b\mid a)=1$ for every $a<u$. Zero probabilities are permitted. Positivity of $u,w$ is not separately required: the law for $p$ forces $S$ to be nonempty, but if $X$ is empty the conditions on $q$ are vacuous, so $u=0$ is possible; when $u=0$, the conditions on $r$ are also vacuous and $w=0$ is possible.

QAlgorithms.Papers.Independent.Intakethird100.P76.BlockSample

For types $S,X,Y,Z$, with $S$ finite, a natural number $n$, and a code $C$ of length $n$ whose positive message count is $M$, this abbreviation denotes the Cartesian product

$$\{0,\ldots,M-1\}\times S^n\times X^n\times Y^n\times Z^n.$$

Thus an element is a tuple $(m,s,x,y,z)$ containing a message and four length-$n$ words. Membership imposes no condition involving the encoder or any channel probabilities, so tuples with zero probability are included. When $n=0$, all four word spaces are singletons, leaving only the message coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P76.BoundedRanges

Let $S$ be a finite type, let $X,Y$ be types, let $R\in\mathbb R$, and let $C_n$, for every natural number $n$, be a sender-excited code of block length $n+1$. Such a code has positive integer message, public-message, and key alphabet sizes $M_n,P_n,K_n$; a probability distribution on $S^{n+1}$ for each message; deterministic public-message and Alice-key maps depending on the message and the $X^{n+1}$ observation; and a deterministic Bob-key map depending on the $Y^{n+1}$ observation and public message. The predicate asserts that there exist fixed real numbers $r_M,r_P\geq0$ such that, for every $n\geq0$,

$$M_n=2^{\lceil(n+1)r_M\rceil_{\mathbb N}},\qquad P_n=2^{\lceil(n+1)r_P\rceil_{\mathbb N}},\qquad K_n=2^{\lceil(n+1)R\rceil_{\mathbb N}}.$$

Here $\lceil t\rceil_{\mathbb N}$ is the least natural number at least $t$, and is $0$ when $t\leq0$. These are exact equalities for every positive block length, including length $1$. There is no hypothesis that $R\geq0$; if $R\leq0$, every $K_n$ equals $1$. Either auxiliary rate may also be $0$, making the corresponding alphabet size $1$.

QAlgorithms.Papers.Independent.Intakethird100.P76.CodeCost

For types $S,X,Y$, with $S$ finite, a natural number $n$, a function $\mathrm{cost}:S\to\mathbb R$, an optional real bound $\Gamma$, and a length-$n$ code $C$ with encoder $e$, this predicate is always true when no bound is supplied. When $\Gamma$ supplies a real number $g$, it means

$$\forall m,\ \forall s\in S^n,\qquad e(m,s)>0\ \Longrightarrow\ \sum_{i=0}^{n-1}\mathrm{cost}(s_i)\le ng.$$

Neither $g$ nor the costs are required to be nonnegative. Words of zero encoder probability impose no condition. For $n=0$, the required inequality is $0\le0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.CostFeasibleInput

For a finite type $S$, functions $\mathrm{cost},p:S\to\mathbb R$, and a real number $\Gamma$, this predicate means that $p(s)\ge0$ for every $s\in S$, $\sum_{s\in S}p(s)=1$, and

$$\sum_{s\in S}p(s)\,\mathrm{cost}(s)\le\Gamma.$$

There is no requirement that the costs or $\Gamma$ be nonnegative. If $S$ is empty, the normalization condition cannot hold.

QAlgorithms.Papers.Independent.Intakethird100.P76.DMBC

For types $S,X,Y,Z$, with specified finite enumerations of $X,Y,Z$, this structure consists of evidence that each of $S,X,Y,Z$ is nonempty, together with a function $w:S\to X\times Y\times Z\to\mathbb R$ satisfying

$$w(s,(x,y,z))\ge0 \quad\text{for every }s,x,y,z, \qquad \sum_{(x,y,z)\in X\times Y\times Z}w(s,(x,y,z))=1 \quad\text{for every }s\in S.$$

No finiteness assumption is imposed on $S$. If any of the four types is empty, no such structure can exist.

QAlgorithms.Papers.Independent.Intakethird100.P76.EntropyRate

For finite types $S,X,Y,Z$, a channel $W$ with nonempty alphabets and conditional probability laws $w_s$, a family $C_n$ of codes of length $n+1$, and a real number $R$, let $M_n>0$, $e_n$, and $a_n$ be each code’s message count, normalized encoder probabilities, and Alice key map. On tuples $o=(m,s,x,y,z)$ of length $n+1$, put

$$P_n(o)=\frac1{M_n}e_n(m,s)\prod_{i=0}^{n}w_{s_i}(x_i,y_i,z_i),\qquad H_n=-\sum_oP_n(o)\log_2\!\left( \sum_{t:\,a_n(t_m,t_x)=a_n(m,x)}P_n(t)\right),$$

where $t_m,t_x$ denote the message and $X$-word of $t$, and the total real logarithm has value $0$ at $0$. The predicate means that for every real $\varepsilon>0$, there is a natural number $N$ such that every $n\ge N$ satisfies $R-\varepsilon\le H_n/(n+1)$. It imposes no nonnegativity assumption on $R$, and requires this eventual lower bound rather than convergence to $R$.

QAlgorithms.Papers.Independent.Intakethird100.P76.InteractiveAchievable

Let $S,X,Y,Z$ be finite nonempty alphabets, let $W_s(x,y,z)\geq0$ sum to $1$ for every $s$, let $\operatorname{cost}:S\to\mathbb R$, and let $\Gamma,R\in\mathbb R$. The predicate asserts $R\geq0$ and the existence of an interactive code $C_n$ of every length $N=n+1$, $n\geq0$. Its underlying sender-excited code has positive alphabet sizes $M_n,P_n,K_n$, a conditional probability distribution $e_n(m,s^N)$, and deterministic public-message and key maps of the sender-excited-code type. There exist fixed $r_M,r_P\geq0$ such that, for every $n$, $M_n=2^{\lceil Nr_M\rceil_{\mathbb N}}$, $P_n=2^{\lceil Nr_P\rceil_{\mathbb N}}$, and $K_n=2^{\lceil NR\rceil_{\mathbb N}}$; moreover, $e_n(m,s^N)>0$ implies $\sum_i\operatorname{cost}(s_i)\leq N\Gamma$. The interactive code additionally has a positive integer $B_n$ of Bob seeds, a natural number $T_n$ of rounds, a positive finite discussion alphabet, a specified Alice-or-Bob sender for each round, deterministic discussion maps depending on the sender’s local data and preceding transcript, and deterministic final-key maps $\alpha_n(m,x^N,\tau)$ and $\beta_n(b,y^N,\tau)$ taking values in the underlying $K_n$-element key alphabet. For $o=(m,s^N,x^N,y^N,z^N,b)$, give the sample mass

$$q_n(o)=\frac{1}{M_nB_n}\,e_n(m,s^N)\prod_iW_{s_i}(x_i,y_i,z_i).$$

Starting with the empty transcript, append at each of the $T_n$ rounds the prescribed sender’s discussion symbol, thereby obtaining $\tau_n(o)$; put $A_n(o)=\alpha_n(m,x^N,\tau_n(o))$ and $V_n(o)=(z^N,\tau_n(o))$. Define $H_q(T)=-\sum_o q(o)\log_2(\sum_{o':T(o')=T(o)}q(o'))$ and $I_q(T;U)=H_q(T)+H_q(U)-H_q(T,U)$, using the total real logarithm, for which $\log_2 0=0$. For every $\varepsilon>0$, eventually $R-\varepsilon\leq H_{q_n}(A_n)/N$, and

$$\sum_o q_n(o)\mathbf1_{\{A_n(o)\ne\beta_n(b,y^N,\tau_n(o))\}}\longrightarrow0,\qquad \frac{I_{q_n}(A_n;V_n)}{N}\longrightarrow0.$$

Zero discussion rounds are allowed. No growth bound on the number of rounds, Bob seeds, or discussion symbols is included, and neither nonnegativity of the cost function nor positivity of $\Gamma$ is assumed.

QAlgorithms.Papers.Independent.Intakethird100.P76.InteractiveCode

For a finite type $S$, arbitrary types $X,Y$, and any natural block length $n$, an interactive code consists of a base code, a positive natural number $B$ of Bob seeds, a natural number $r$ of rounds, a positive natural number $d$ of transcript symbols, a function $\operatorname{sender}:\mathbb N\to\{\mathrm{false},\mathrm{true}\}$, and four functions

$$\begin{aligned} \operatorname{AliceTalk}&:\{0,\ldots,M-1\}\times X^n\times\operatorname{List}(\{0,\ldots,d-1\})\to\{0,\ldots,d-1\},\\ \operatorname{BobTalk}&:\{0,\ldots,B-1\}\times Y^n\times\operatorname{List}(\{0,\ldots,d-1\})\to\{0,\ldots,d-1\},\\ \operatorname{FinalAlice}&:\{0,\ldots,M-1\}\times X^n\times\operatorname{List}(\{0,\ldots,d-1\})\to\{0,\ldots,K-1\},\\ \operatorname{FinalBob}&:\{0,\ldots,B-1\}\times Y^n\times\operatorname{List}(\{0,\ldots,d-1\})\to\{0,\ldots,K-1\}. \end{aligned}$$

The base code supplies positive natural message, public-message, and key counts $M,P,K$, a nonnegative normalized encoder $e(s^n\mid m)$, a public map $\{0,\ldots,M-1\}\times X^n\to\{0,\ldots,P-1\}$, an Alice key map $\{0,\ldots,M-1\}\times X^n\to\{0,\ldots,K-1\}$, and a Bob key map $Y^n\times\{0,\ldots,P-1\}\to\{0,\ldots,K-1\}$. No further relationship between the base maps and the four interactive functions is required. The functions are defined on every finite transcript list, the sender function is defined at every natural index, and $r=0$ and $n=0$ are allowed.

QAlgorithms.Papers.Independent.Intakethird100.P76.InteractiveSample

For a finite type $S$, arbitrary types $X,Y,Z$, a natural block length $n$, and an interactive code $C$, let $M>0$ be its base message count and $B>0$ its Bob-seed count. The declaration abbreviates the sample type as

$$\{0,\ldots,M-1\}\times S^n\times X^n\times Y^n\times Z^n\times\{0,\ldots,B-1\},$$

with an element represented by $((m,s^n,x^n,y^n,z^n),b)$. This is the base sample—one message and four length-$n$ words—paired with a Bob seed; it imposes no probability law or encoder-support restriction on its elements. For $n=0$, each word space contains its unique empty word, including when its alphabet is empty.

QAlgorithms.Papers.Independent.Intakethird100.P76.SenderExcitedCode

For types $S,X,Y$, with $S$ finite, and a natural number $n$, a code consists of positive natural numbers $M,L,K$, respectively specifying the numbers of messages, public labels, and keys; an encoder $e:\{0,\ldots,M-1\}\times S^n\to\mathbb R$ satisfying $e(m,s)\ge0$ and $\sum_{s\in S^n}e(m,s)=1$ for every message $m$; and deterministic functions

$$f:\{0,\ldots,M-1\}\times X^n\to\{0,\ldots,L-1\},\qquad a:\{0,\ldots,M-1\}\times X^n\to\{0,\ldots,K-1\},\qquad b:Y^n\times\{0,\ldots,L-1\}\to\{0,\ldots,K-1\}.$$

These are the public map, Alice’s key map, and Bob’s key map. No correctness, secrecy, or cost condition is imposed. The length $n=0$ is allowed, and each zero-length word space is a singleton. No finiteness or nonemptiness assumption on $X$ or $Y$ is required here; if $S$ is empty and $n>0$, the encoder normalization is impossible.

QAlgorithms.Papers.Independent.Intakethird100.P76.SenderExcitedDegraded

For finite nonempty alphabets $S,X,Y,Z$ and conditional probabilities $W_s(x,y,z)\ge0$ summing to $1$ over $x,y,z$ for each $s$, this predicate means that there exists a function $d:Y\times Z\to\mathbb R$ such that $d(y,z)\ge0$ and $\sum_z d(y,z)=1$ for every $y$, and, for every $s\in S$, $x\in X$, and $z\in Z$,

$$\sum_{y\in Y}W_s(x,y,z) = \sum_{y\in Y}\left(\sum_{t\in Z}W_s(x,y,t)\right)d(y,z).$$

The same $d$ is used for all $s,x$. The required equality concerns these marginals; it does not require $W_s(x,y,z)$ itself to factor as $\bigl(\sum_tW_s(x,y,t)\bigr)d(y,z)$.

QAlgorithms.Papers.Independent.Intakethird100.P76.StrongAchievable

For finite nonempty alphabets $S,X,Y,Z$, a channel $W$ whose nonnegative conditional masses $W_s(x,y,z)$ sum to $1$, and a real rate $R$, this predicate means that there exist strictly positive real numbers $E,F$ such that $R\ge0$ and a code sequence satisfies the following conditions. For each $n\ge0$, the code has length $L=n+1$, positive finite message, public-message, and key sizes $M_n,P_n,K_n$, a stochastic encoder $e_n(m,s^L)$, and deterministic public, Alice-key, and Bob-key maps $a_n(m,x^L)$, $k_n(m,x^L)$, and $b_n(y^L,a)$. Its sample mass is

$$\mu_n(m,s^L,x^L,y^L,z^L) =M_n^{-1}e_n(m,s^L)\prod_iW_{s_i}(x_i,y_i,z_i).$$

For fixed $r_M,r_P,r_K\ge0$, the sizes satisfy $M_n=2^{\lceil Lr_M\rceil}$, $P_n=2^{\lceil Lr_P\rceil}$, and $K_n\le2^{Lr_K}$. Let $A_n=k_n(m,x^L)$, $V_n=(z^L,a_n(m,x^L))$, $d_n=\Pr[A_n\ne b_n(y^L,a_n(m,x^L))]$, and $\ell_n=I_{\mu_n}(A_n;V_n)$, where

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right), \qquad I_\mu(A;B)=H_\mu(A)+H_\mu(B)-H_\mu(A,B).$$

For every $\varepsilon>0$, eventually $H_{\mu_n}(A_n)/L\ge R-\varepsilon$, and $E\le\liminf_n g_n(d_n)$, $F\le\liminf_n g_n(\ell_n)$, with $g_n(0)=+\infty$ and $g_n(t)=-\log_2(t)/(n+1)$ for $t\ne0$. No cost constraint is part of this predicate.

QAlgorithms.Papers.Independent.Intakethird100.P76.StrongAchievableAt

Let $S,X,Y,Z$ be finite nonempty alphabets, and let $W$ assign to each $s\in S$ a probability distribution $W_s(x,y,z)$ on $X\times Y\times Z$. For real numbers $R_K,R_P,R_M$, this property means that all three rates are nonnegative and there exist real numbers $E,F>0$ and a code $C_n$ of length $N=n+1$ for every natural number $n$, including $n=0$, with exactly

$$M_n=2^{\lceil NR_M\rceil_+},\qquad L_n=2^{\lceil NR_P\rceil_+},\qquad K_n=2^{\lceil NR_K\rceil_+}$$

messages, public symbols, and key symbols, respectively, where $\lceil\cdot\rceil_+$ is the natural-number ceiling. Each code consists of a probability distribution $e_{n,m}$ on $S^N$ for every message $m$, a public map $T_n:\{0,\ldots,M_n-1\}\times X^N\to\{0,\ldots,L_n-1\}$, an Alice key map $A_n:\{0,\ldots,M_n-1\}\times X^N\to\{0,\ldots,K_n-1\}$, and a Bob key map $B_n:Y^N\times\{0,\ldots,L_n-1\}\to\{0,\ldots,K_n-1\}$. All probabilities below use the finite sample law

$$P_n(m,s^N,x^N,y^N,z^N) =\frac{e_{n,m}(s^N)}{M_n}\prod_{i=0}^{N-1}W_{s_i}(x_i,y_i,z_i).$$

Write $a_n=P_n\{A_n(m,x^N)\ne B_n(y^N,T_n(m,x^N))\}$ and $b_n=I_{P_n}(A_n(m,x^N);(z^N,T_n(m,x^N)))$, where $H(U)=-\sum_u P(U=u)\log_2P(U=u)$, $H(U\mid V)=H(U,V)-H(V)$, and $I(U;V)=H(U)+H(V)-H(U,V)$, with zero-probability summands equal to zero. For every real $\varepsilon>0$, eventually in $n$,

$$R_K-\varepsilon\le \frac{H_{P_n}(A_n(m,x^N))}{n+1}.$$

Furthermore, defining the extended-real quantity

$$\ell_n(t)= \begin{cases} +\infty,&t=0,\\ -\dfrac{\log_2t}{n+1},&t\ne0, \end{cases}$$

one has

$$E\le\liminf_{n\to\infty}\ell_n(a_n), \qquad F\le\liminf_{n\to\infty}\ell_n(b_n).$$

Thus zero disagreement or zero leakage contributes $+\infty$ to its corresponding logarithmic rate; a zero prescribed rate gives a corresponding alphabet of size one. The definition imposes no input-cost condition.

QAlgorithms.Papers.Independent.Intakethird100.P76.TripleAchievable

Let $S,X,Y,Z$ be finite nonempty alphabets, let $W_s(x,y,z)\geq0$ sum to $1$ for every $s$, and write the given real triple as $v=(R,E,F)$. The predicate asserts $R,E,F\geq0$ and the existence of codes $C_n$ of every length $N=n+1$, $n\geq0$, with positive message, public-message, and key alphabet sizes $M_n,P_n,K_n$; conditional probability distributions $e_n(m,s^N)$; and deterministic public-message, Alice-key, and Bob-key maps $\pi_n(m,x^N)$, $a_n(m,x^N)$, and $b_n(y^N,\pi)$. There must be fixed $r_M,r_P\geq0$ such that

$$M_n=2^{\lceil Nr_M\rceil_{\mathbb N}},\qquad P_n=2^{\lceil Nr_P\rceil_{\mathbb N}},\qquad K_n=2^{\lceil NR\rceil_{\mathbb N}}$$

for every $n$. Give $o=(m,s^N,x^N,y^N,z^N)$ mass $q_n(o)=M_n^{-1}e_n(m,s^N)\prod_iW_{s_i}(x_i,y_i,z_i)$, put $A_n=a_n(m,x^N)$ and $V_n=(z^N,\pi_n(m,x^N))$, and define $H_q(T)=-\sum_o q(o)\log_2(\sum_{o':T(o')=T(o)}q(o'))$ and $I_q(T;U)=H_q(T)+H_q(U)-H_q(T,U)$. For every $\varepsilon>0$, eventually $R-\varepsilon\leq H_{q_n}(A_n)/N$. Writing

$$d_n=\sum_o q_n(o)\mathbf1_{\{A_n(o)\ne b_n(y^N,\pi_n(m,x^N))\}},\qquad \ell_n=I_{q_n}(A_n;V_n),\qquad L_N(t)= \begin{cases} +\infty,&t=0,\\ -\log_2(t)/N,&t\ne0, \end{cases}$$

the remaining requirements, in the extended real numbers, are

$$E\leq\liminf_{n\to\infty}L_{n+1}(d_n),\qquad F\leq\liminf_{n\to\infty}L_{n+1}(\ell_n).$$

The natural ceiling is truncated at $0$, and $\log_2 0=0$ in the entropy definitions. No cost condition is present. The allowed exponents include $E=0$ and $F=0$; the predicate does not separately require either $d_n$ or $\ell_n$ to tend to $0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.WeakAchievable

Let $S,X,Y,Z$ be finite types, and let $W$ specify nonempty alphabets and, for every $s\in S$, nonnegative numbers $W_s(x,y,z)$ summing to $1$ over $X\times Y\times Z$. Let $\operatorname{cost}:S\to\mathbb R$, let $\Gamma$ be either absent or a specified real number, and let $R\in\mathbb R$. The predicate asserts $R\geq0$ and the existence, for every $n\geq0$, of a code $C_n$ of length $N=n+1$, with positive integers $M_n,P_n,K_n$, conditional probability distributions $e_n(m,s^N)$ on $S^N$, and deterministic maps $\pi_n(m,x^N)\in\{0,\ldots,P_n-1\}$, $a_n(m,x^N)\in\{0,\ldots,K_n-1\}$, and $b_n(y^N,\pi)\in\{0,\ldots,K_n-1\}$, satisfying the following requirements. There exist fixed $r_M,r_P\geq0$ such that $M_n=2^{\lceil Nr_M\rceil_{\mathbb N}}$, $P_n=2^{\lceil Nr_P\rceil_{\mathbb N}}$, and $K_n=2^{\lceil NR\rceil_{\mathbb N}}$ for every $n$. If $\Gamma=g$ is specified, then every $m,s^N$ with $e_n(m,s^N)>0$ satisfies $\sum_{i=0}^{N-1}\operatorname{cost}(s_i)\leq Ng$; an absent $\Gamma$ imposes no cost condition. On the finite sample space of tuples $o=(m,s^N,x^N,y^N,z^N)$, put

$$q_n(o)=M_n^{-1}e_n(m,s^N)\prod_{i=0}^{N-1}W_{s_i}(x_i,y_i,z_i),\qquad A_n(o)=a_n(m,x^N),\qquad V_n(o)=(z^N,\pi_n(m,x^N)).$$

For any finite probability mass function $q$ and observation $T$, define

$$H_q(T)=-\sum_o q(o)\log_2\!\left(\sum_{o':\,T(o')=T(o)}q(o')\right),\qquad I_q(T;U)=H_q(T)+H_q(U)-H_q(T,U).$$

For every real $\varepsilon>0$, eventually $R-\varepsilon\leq H_{q_n}(A_n)/N$, and

$$\sum_o q_n(o)\,\mathbf1_{\{A_n(o)\ne b_n(y^N,\pi_n(m,x^N))\}}\longrightarrow0,\qquad \frac{I_{q_n}(A_n;V_n)}{N}\longrightarrow0$$

as $n\to\infty$. The real logarithm is total, with $\log_2 0=0$, so zero-mass terms are included under that convention. No positivity or boundedness assumption on the cost function or specified cost limit is imposed.

QAlgorithms.Papers.Independent.Intakethird100.P76.advantage

For finite nonempty alphabets $S,X,Y,Z$, a channel $W$ with nonnegative conditional masses summing to $1$, and any function $p:S\to\mathbb R$, put $\mu(s,x,y,z)=p(s)W_s(x,y,z)$ and let $\mathsf S,\mathsf X,\mathsf Y,\mathsf Z$ denote the coordinate observations. For any observation $A$, define

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right), \qquad I_\mu(A;B)=H_\mu(A)+H_\mu(B)-H_\mu(A,B).$$

The function returns

$$I_\mu((\mathsf X,\mathsf S);\mathsf Y) - I_\mu((\mathsf X,\mathsf S);\mathsf Z).$$

There is no assumption that $p$ is nonnegative or sums to $1$; the displayed finite-sum expressions are evaluated even then, using the total real logarithm, with $\log_2 0=0$ and $\log_2 t=\log_2|t|$ for $t<0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.auxMass

For finite types $S,X,Y,Z$, a channel datum $W$ supplies their nonemptiness and numbers $W_s(x,y,z)\ge0$ with $\sum_{x,y,z}W_s(x,y,z)=1$ for every $s\in S$. Given natural numbers $u,w$ and an auxiliary datum $A$, write its input law as $p(s)$, its first stochastic kernel as $q(a\mid x,s)$, and its second stochastic kernel as $r(b\mid a)$; thus these functions are nonnegative and each relevant distribution sums to one. The declaration defines the real-valued mass function on tuples $(b,a,s,x,y,z)\in\{0,\ldots,w-1\}\times\{0,\ldots,u-1\}\times S\times X\times Y\times Z$ by

$$\mu(b,a,s,x,y,z)=r(b\mid a)\,q(a\mid x,s)\,p(s)\,W_s(x,y,z).$$

Although $u,w$ are introduced as arbitrary natural numbers, existence of $A$ with the nonempty types supplied by $W$ forces both to be positive.

QAlgorithms.Papers.Independent.Intakethird100.P76.auxObjective

For finite types $S,X,Y,Z$, a channel datum $W$ giving nonempty types and conditional probability laws $W_s(x,y,z)$, natural numbers $u,w$, and auxiliary data consisting of an input law $p$ and stochastic kernels $q(a\mid x,s)$, $r(b\mid a)$, form the mass function $\mu(b,a,s,x,y,z)=r(b\mid a)q(a\mid x,s)p(s)W_s(x,y,z)$. Let $U,V,Y,Z$ denote, respectively, the coordinates $a,b,y,z$. For any observation $F$ of this finite sample space, define

$$H_\mu(F)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,F(o')=F(o)}\mu(o')\right),$$

with zero-mass terms contributing zero. The declaration defines the objective to be

$$\bigl[H_\mu(U,V)-H_\mu(V)-H_\mu(U,Y,V)+H_\mu(Y,V)\bigr] -\bigl[H_\mu(U,V)-H_\mu(V)-H_\mu(U,Z,V)+H_\mu(Z,V)\bigr],$$

that is, $I_\mu(U;Y\mid V)-I_\mu(U;Z\mid V)$. Neither auxiliary kernel is required to be deterministic or strictly positive.

QAlgorithms.Papers.Independent.Intakethird100.P76.auxValues

For finite types $S,X,Y,Z$, a channel datum $W$ giving nonempty types and conditional probability laws $W_s(x,y,z)$, any real-valued cost function $c:S\to\mathbb R$, and any real number $\Gamma$, the declaration defines a set of real numbers as follows: $v$ belongs to it exactly when there are positive natural numbers $u,w$, a probability law $p$ on $S$, and stochastic kernels $q(a\mid x,s)$ and $r(b\mid a)$, with $a<u$ and $b<w$, such that $\sum_s p(s)c(s)\le\Gamma$ and

$$v=I_\mu(U;Y\mid V)-I_\mu(U;Z\mid V),\qquad \mu(b,a,s,x,y,z)=r(b\mid a)q(a\mid x,s)p(s)W_s(x,y,z).$$

Here all laws and kernels are nonnegative and normalized, $U=a,V=b$, and $I_\mu(A;B\mid C)=H_\mu(A,C)-H_\mu(C)-H_\mu(A,B,C)+H_\mu(B,C)$, using Shannon entropy in bits and zero contribution from zero-probability terms. No sign or boundedness condition on $c$, and no positivity condition on $\Gamma$, is imposed by this definition; if no feasible input law exists, the defined set is empty.

QAlgorithms.Papers.Independent.Intakethird100.P76.blockMass

Let $S,X,Y,Z$ be finite types, let $W$ specify nonempty $S,X,Y,Z$ and, for each $s\in S$, nonnegative numbers $w_s(x,y,z)$ summing to $1$ over $X\times Y\times Z$, and let $C$ be a length-$n$ code with positive message count $M$ and encoder probabilities $e(m,s)$ summing to $1$ over $s\in S^n$ for each message. This function assigns to every tuple $o=(m,s,x,y,z)$ the real number

$$P(o)=\frac1M\,e(m,s)\prod_{i=0}^{n-1}w_{s_i}(x_i,y_i,z_i).$$

The code’s public and key maps do not enter this expression. The natural number $n$ may be zero; then the product is $1$, and encoder normalization makes the mass of each message tuple $1/M$.

QAlgorithms.Papers.Independent.Intakethird100.P76.channelRate

For finite nonempty alphabets $S,X,Y,Z$, a channel $W$ whose nonnegative conditional masses sum to $1$, and an arbitrary function $p:S\to\mathbb R$, put $\mu(s,x,y,z)=p(s)W_s(x,y,z)$ and let $\mathsf S,\mathsf Y,\mathsf Z$ be the corresponding coordinate observations. Define

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right).$$

This function returns

$$\bigl[H_\mu(\mathsf S)+H_\mu(\mathsf Y)-H_\mu(\mathsf S,\mathsf Y)\bigr] - \bigl[H_\mu(\mathsf S)+H_\mu(\mathsf Z)-H_\mu(\mathsf S,\mathsf Z)\bigr].$$

There is no assumption that $p$ is a probability distribution. These expressions remain defined for zero or negative masses through the total real logarithm, for which $\log_2 0=0$ and $\log_2 t=\log_2|t|$ when $t<0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.condEntropy

For any finite type $O$, arbitrary types $A,B$, any function $p:O\to\mathbb R$, and observations $a:O\to A$, $b:O\to B$, this defines

$$-\sum_{o\in O}p(o)\log_2\!\left(\sum_{\substack{t\in O\\a(t)=a(o),\ b(t)=b(o)}}p(t)\right) +\sum_{o\in O}p(o)\log_2\!\left(\sum_{\substack{t\in O\\b(t)=b(o)}}p(t)\right).$$

No nonnegativity or normalization is required of $p$, and neither observation type is required to be finite. The logarithm has value $0$ at $0$ and uses the absolute value at negative arguments. The definition gives $0$ when $O$ is empty.

QAlgorithms.Papers.Independent.Intakethird100.P76.condInfo

For any finite type $O$, arbitrary types $A,B,C$, any function $p:O\to\mathbb R$, and observations $a:O\to A$, $b:O\to B$, $c:O\to C$, write $m_c(o)=\sum_{t:c(t)=c(o)}p(t)$, $m_{ac}(o)=\sum_{t:a(t)=a(o),\,c(t)=c(o)}p(t)$, $m_{bc}(o)=\sum_{t:b(t)=b(o),\,c(t)=c(o)}p(t)$, and $m_{abc}(o)=\sum_{t:a(t)=a(o),\,b(t)=b(o),\,c(t)=c(o)}p(t)$. This defines

$$-\sum_o p(o)\log_2 m_{ac}(o) +\sum_o p(o)\log_2 m_c(o) +\sum_o p(o)\log_2 m_{abc}(o) -\sum_o p(o)\log_2 m_{bc}(o).$$

There are no probability assumptions on $p$ or finiteness assumptions on $A,B,C$. The logarithm is $0$ at $0$ and uses absolute values at negative arguments. If $O$ is empty, the result is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.eveView

For types $S,X,Y,Z$, with $S$ finite, a natural number $n$, a length-$n$ code $C$ with positive message and public-label counts $M,L$, and a tuple $o=(m,s,x,y,z)\in\{0,\ldots,M-1\}\times S^n\times X^n\times Y^n\times Z^n$, this function returns

$$\bigl(z,f(m,x)\bigr)\in Z^n\times\{0,\ldots,L-1\},$$

where $f$ is the code’s public map. This is defined for every tuple, including tuples of zero probability, and for $n=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.excitationJointMass

For types $S,X,Y,Z$, with finite $X,Y,Z$, let $W$ consist of nonemptiness evidence for all four types and a function $w(s,(x,y,z))$ that is nonnegative and sums to $1$ over $(x,y,z)$ for each $s$. For any function $p:S\to\mathbb R$, this defines a function on quadruples by

$$(s,x,y,z)\longmapsto p(s)\,w(s,(x,y,z)).$$

No nonnegativity or normalization is assumed for $p$, and no finiteness of $S$ is required.

QAlgorithms.Papers.Independent.Intakethird100.P76.generatedKeyEntropy

For finite types $S,X,Y,Z$, a channel $W$ with nonempty alphabets and conditional probability laws $w_s$, and a length-$n$ code $C$ with positive message count $M$, normalized encoder probabilities $e$, and Alice key map $a$, let

$$P(m,s,x,y,z)=\frac1M e(m,s)\prod_{i=0}^{n-1}w_{s_i}(x_i,y_i,z_i).$$

This real number is

$$-\sum_{o=(m,s,x,y,z)}P(o)\log_2\!\left( \sum_{\substack{o'=(m',s',x',y',z')\\a(m',x')=a(m,x)}}P(o') \right).$$

The logarithm is the total real base-$2$ logarithm, with value $0$ at $0$. There is no requirement that the generated key be uniform. The natural number $n$ may be zero, with the product in $P$ then equal to $1$.

QAlgorithms.Papers.Independent.Intakethird100.P76.innerRegion

Let $S,X,Y,Z$ be finite nonempty sets, let each $W_s(x,y,z)$ be a probability distribution, and fix any function $p:S\to\mathbb R$ and real numbers $R_P,R_M$. Write $A_s(x,y)=\sum_zW_s(x,y,z)$, $B_s(y)=\sum_xA_s(x,y)$, $C_s(x,z)=\sum_yW_s(x,y,z)$, and $p_Z(z)=\sum_{s,x}p(s)C_s(x,z)$. For $r\in[0,1]$, set

$$\begin{aligned} F_1(r)&=rR_P-\log_2\!\sum_{s,y}p(s)B_s(y) \left[\sum_x\left(\frac{A_s(x,y)}{B_s(y)}\right)^{1/(1+r)}\right]^{1+r},\\ F_2(r)&=r(R_P-R_M)-\log_2\!\sum_{x,y} \left[\sum_sp(s)A_s(x,y)^{1/(1+r)}\right]^{1+r},\\ F_3(r)&=r(R_P-R_M)-\log_2\!\sum_y \left[\sum_{s,x}p(s)A_s(x,y)^{1/(1+r)}\right]^{1+r}, \end{aligned}$$

and set

$$G(\alpha,R)=-\alpha(R+R_P-R_M)-\log_2\!\sum_z \begin{cases} 0,&p_Z(z)=0,\\ \displaystyle\sum_{s,x}p(s)C_s(x,z) \left(\frac{C_s(x,z)}{p_Z(z)}\right)^\alpha,&p_Z(z)\ne0. \end{cases}$$

The declaration defines the set of triples $(R,E,F)\in\mathbb R^3$ satisfying

$$R,E,F\ge0,\qquad E\le\min\left\{\sup_{r\in[0,1]}F_1(r), \min\left\{\sup_{r\in[0,1]}F_2(r),\sup_{r\in[0,1]}F_3(r)\right\}\right\}, \qquad F\le\sup_{0<\alpha\le1}G(\alpha,R).$$

The comparisons and suprema are in the extended real line after embedding the real quantities. The function $p$ need not be a probability distribution, and $R_P,R_M$ need not be nonnegative. Zero coordinates $R,E,F$ are allowed; all powers, divisions, and logarithms are total, with division by zero and $\log_2 0$ equal to zero.

QAlgorithms.Papers.Independent.Intakethird100.P76.inputOptimizedSecrecyExponent

For finite, nonempty alphabets $S,X,Y,Z$, let $W$ specify numbers $w_s(x,y,z)\ge0$ summing to one over $(x,y,z)$ for every $s$, and let $R_K,R_P,R_M$ be arbitrary real numbers. Put $c_s(x,z)=\sum_y w_s(x,y,z)$. For a probability distribution $p:S\to\mathbb R$, meaning $p\ge0$ and $\sum_s p(s)=1$, put $q_p(z)=\sum_{s,x}p(s)c_s(x,z)$. The declaration defines the extended-real supremum

$$\sup_{\substack{p:S\to\mathbb R\\p\ge0,\ \sum_s p(s)=1}} \ \sup_{\alpha\in(0,1]} \left[ -\alpha(R_K+R_P-R_M) -\log_2\!\left( \sum_z \begin{cases} 0,&q_p(z)=0,\\[2pt] \displaystyle\sum_{s,x}p(s)c_s(x,z) \left(\frac{c_s(x,z)}{q_p(z)}\right)^\alpha, &q_p(z)\ne0 \end{cases} \right) \right].$$

Each bracketed real value is embedded into the extended reals before taking the suprema. Distributions with zero entries are allowed, the zero-$q_p(z)$ branch contributes exactly zero, and the total real logarithm has $\log_2 0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.interactiveCapacity

For finite nonempty alphabets $S,X,Y,Z$, conditional probability distributions $W_s(x,y,z)$, an arbitrary cost function $c:S\to\mathbb R$, and $\Gamma\in\mathbb R$, this declaration defines an extended-real number as the supremum of the real rates $R\ge0$ satisfying the following condition, embedded into the extended real line. There must exist interactive codes of every positive length $N$, with positive base message, public-label, and key counts $M_N,P_N,K_N$, conditional encoder distributions $e_{N,m}$ on $S^N$, positive finite Bob-seed counts $B_N$, finite positive transcript alphabets, finite fixed speaking schedules, and deterministic speaking and final-key functions. Fixed constants $r_M,r_P,r_K\ge0$ must give $M_N=2^{\lceil Nr_M\rceil_+}$, $P_N=2^{\lceil Nr_P\rceil_+}$, and $K_N\le2^{Nr_K}$ for every $N\ge1$; every encoder-supported word must satisfy $\sum_{i<N}c(s_i)\le N\Gamma$. Under the sample weights $e_{N,m}(s^N)(M_NB_N)^{-1}\prod_{i<N}W_{s_i}(x_i,y_i,z_i)$, let $T_N$ be the transcript produced by successively applying the scheduled Alice functions of $m,x^N$ and the preceding transcript and Bob functions of his seed, $y^N$, and that transcript, and let $A_N,B'_N$ be the resulting final keys. For every $\varepsilon>0$, eventually $H(A_N)/N\ge R-\varepsilon$, while $\Pr(A_N\ne B'_N)\to0$ and $I(A_N;(Z^N,T_N))/N\to0$, with entropies in bits. The supremum is taken in the extended real line, so an empty set gives $-\infty$ and an unbounded set gives $+\infty$.

QAlgorithms.Papers.Independent.Intakethird100.P76.interactiveEntropy

For finite nonempty alphabets $S,X,Y,Z$, let $W_s$ be a probability distribution on $X\times Y\times Z$, and let $C$ be an interactive code of natural length $n$, possibly zero. If $M,B>0$ are its numbers of base messages and Bob seeds and $e_m$ is its conditional distribution on $S^n$, assign each sample $o=(m,s^n,x^n,y^n,z^n,b)$ weight $\mu(o)=e_m(s^n)(MB)^{-1}\prod_{i<n}W_{s_i}(x_i,y_i,z_i)$. Its transcript $T(o)$ starts empty and successively appends symbols according to the fixed speaking schedule, using Alice’s functions of $m,x^n$ and the preceding transcript or Bob’s functions of $b,y^n$ and that transcript. Let $A(o)$ be Alice’s final-key function of $m,x^n,T(o)$. The declaration defines the real number

$$-\sum_o\mu(o)\log_2\!\left(\sum_{o':A(o')=A(o)}\mu(o')\right),$$

the entropy in bits of Alice’s final key under these weights. This uses the actual key distribution; zero probabilities use the total-real convention $\log_2 0=0$, and for $n=0$ the channel product is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P76.interactiveError

For finite nonempty alphabets $S,X,Y,Z$, let $W_s(x,y,z)\ge 0$ satisfy $\sum_{x,y,z}W_s(x,y,z)=1$ for every $s\in S$, and let $C$ be an interactive code of length $n\in\mathbb N$, including $n=0$. Its base code has positive numbers $M,P,K$ of messages, public labels, and keys, and conditional probabilities $e_m(s^n)\ge0$ with $\sum_{s^n}e_m(s^n)=1$. The interactive code also has a positive number $B$ of Bob seeds, a finite number of rounds, a positive finite transcript alphabet, a fixed schedule specifying the speaker in each round, and deterministic speaking and final-key functions. A sample $o=(m,s^n,x^n,y^n,z^n,b)$, with $m<M$ and $b<B$, has weight

$$\mu(o)=\frac{e_m(s^n)}{MB}\prod_{i=0}^{n-1}W_{s_i}(x_i,y_i,z_i).$$

Starting with an empty transcript, each scheduled Alice round appends her speaking function of $m,x^n$ and the preceding transcript; each Bob round appends his speaking function of $b,y^n$ and that transcript. Write $T(o)$ for the resulting transcript, $K_A(o)$ for Alice’s final-key function of $m,x^n,T(o)$, and $K_B(o)$ for Bob’s final-key function of $b,y^n,T(o)$. The declaration defines the real number $\sum_{o:K_A(o)\ne K_B(o)}\mu(o)$. Zero rounds give an empty transcript; for $n=0$, the channel product is $1$.

QAlgorithms.Papers.Independent.Intakethird100.P76.interactiveKeyA

For a finite type $S$, arbitrary types $X,Y,Z$, a natural block length $n$, an interactive code $C$, and a sample $((m,s^n,x^n,y^n,z^n),b)$, the declaration defines Alice’s interactive key as $\operatorname{FinalAlice}(m,x^n,t_r)$, an index in the base code’s positive key alphabet $\{0,\ldots,K-1\}$. Here $r$ is the code’s round count, $t_0=[]$, and $t_{i+1}$ is obtained by appending $\operatorname{AliceTalk}(m,x^n,t_i)$ when $\operatorname{sender}(i)=\mathrm{true}$, or $\operatorname{BobTalk}(b,y^n,t_i)$ otherwise, for $0\le i<r$. In particular, when $r=0$, the key is $\operatorname{FinalAlice}(m,x^n,[])$; the declaration does not require this function to equal the base code’s Alice key map.

QAlgorithms.Papers.Independent.Intakethird100.P76.interactiveLeakage

For finite nonempty alphabets $S,X,Y,Z$, let $W_s$ be a probability distribution on $X\times Y\times Z$, and let $C$ be an interactive code of any natural length $n$, including zero. Let $M,B$ be its positive numbers of base messages and Bob seeds, and let $e_m$ be its probability distribution on $S^n$ for message $m$. On samples $o=(m,s^n,x^n,y^n,z^n,b)$, use the weights

$$\mu(o)=\frac{e_m(s^n)}{MB}\prod_{i=0}^{n-1}W_{s_i}(x_i,y_i,z_i).$$

Construct $T(o)$ from the empty transcript by following the code’s fixed finite speaking schedule: Alice’s next symbol depends on $m,x^n$ and the preceding transcript, while Bob’s depends on $b,y^n$ and that transcript. Let $A(o)$ be Alice’s final key computed from $m,x^n,T(o)$, and let $V(o)=(z^n,T(o))$. For any observation $F$, define

$$H_\mu(F)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':F(o')=F(o)}\mu(o')\right).$$

The declaration defines $H_\mu(A)+H_\mu(V)-H_\mu(A,V)$, the mutual information in bits between Alice’s final key and the pair consisting of Eve’s channel observations and the interactive transcript. The logarithm is the total real logarithm used in the supplied code, with $\log_2 0=0$; empty channel products equal $1$, and zero speaking rounds give an empty transcript.

QAlgorithms.Papers.Independent.Intakethird100.P76.interactiveMass

For finite types $S,X,Y,Z$, a channel datum $W$ giving their nonemptiness and nonnegative normalized conditional laws $W_s(x,y,z)$, a natural block length $n$, and an interactive code $C$, let $M>0$ be its base message count, $B>0$ its Bob-seed count, and $e(s^n\mid m)$ its base encoder, which is nonnegative and sums to one over $S^n$ for every message $m$. The declaration defines the mass of a sample $((m,s^n,x^n,y^n,z^n),b)$ to be

$$\frac{1}{MB}\,e(s^n\mid m)\prod_{i=0}^{n-1}W_{s_i}(x_i,y_i,z_i).$$

Thus the formula does not depend on the particular seed index $b$. Both denominators are positive by the code’s fields. For $n=0$, the product is $1$, and encoder normalization on the unique empty input word makes the mass $1/(MB)$.

QAlgorithms.Papers.Independent.Intakethird100.P76.keyA

For types $S,X,Y,Z$, with $S$ finite, a natural number $n$, a length-$n$ code $C$ with positive message and key counts $M,K$, and a tuple $o=(m,s,x,y,z)\in\{0,\ldots,M-1\}\times S^n\times X^n\times Y^n\times Z^n$, this function returns $C$’s Alice key $a(m,x)\in\{0,\ldots,K-1\}$. It uses only the message $m$ and the $X$-word $x$, regardless of the tuple’s probability. The length $n=0$ is included.

QAlgorithms.Papers.Independent.Intakethird100.P76.keyDisagreementProbability

For finite types $S,X,Y,Z$, a channel $W$ with nonempty alphabets and conditional probability laws $w_s$ on $X\times Y\times Z$, and a length-$n$ code $C$, write $M,L,K>0$ for its message, public-label, and key counts, $e(m,s)$ for its normalized encoder probabilities, $f(m,x)$ for its public map, and $a(m,x)$ and $b(y,\ell)$ for its two key maps. This real number is

$$\sum_{\substack{m<M,\ s\in S^n,\ x\in X^n,\ y\in Y^n,\ z\in Z^n\\ a(m,x)\ne b(y,f(m,x))}} \frac1M\,e(m,s)\prod_{i=0}^{n-1}w_{s_i}(x_i,y_i,z_i).$$

Thus only tuples on which the two specified keys differ contribute. Zero-length codes are included, with an empty product equal to $1$.

QAlgorithms.Papers.Independent.Intakethird100.P76.logRate

For every natural number $n$, including $0$, and every real number $t$, this extended-real-valued function is

$$\operatorname{logRate}(n,t)= \begin{cases} +\infty,&t=0,\\[2mm] -\dfrac{\log_2 t}{n+1},&t\ne0. \end{cases}$$

The second branch is a real number embedded in the extended reals, and its denominator is always positive. There is no assumption that $t$ is a probability or even nonnegative: the total real logarithm used here satisfies $\log_2 t=\log_2|t|$ for negative $t$.

QAlgorithms.Papers.Independent.Intakethird100.P76.obsS

For arbitrary types $S,X,Y,Z$ and any quadruple $o=(s,x,y,z)\in S\times X\times Y\times Z$, this defines the $S$-valued observation $o\mapsto s$, its first coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P76.obsX

For arbitrary types $S,X,Y,Z$ and any quadruple $o=(s,x,y,z)\in S\times X\times Y\times Z$, this defines the $X$-valued observation $o\mapsto x$, its second coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P76.obsY

For arbitrary types $S,X,Y,Z$ and any quadruple $o=(s,x,y,z)\in S\times X\times Y\times Z$, this defines the $Y$-valued observation $o\mapsto y$, its third coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P76.obsZ

For arbitrary types $S,X,Y,Z$ and any quadruple $o=(s,x,y,z)\in S\times X\times Y\times Z$, this defines the $Z$-valued observation $o\mapsto z$, its fourth coordinate.

QAlgorithms.Papers.Independent.Intakethird100.P76.observationEntropyBits

For any finite type $O$, any type $A$, any function $p:O\to\mathbb R$, and any observation $a:O\to A$, this defines the real number

$$-\sum_{o\in O}p(o)\log_2\!\left(\sum_{\substack{t\in O\\a(t)=a(o)}}p(t)\right).$$

There is no assumption that $p$ is nonnegative or sums to $1$, and $A$ need not be finite. Here the real logarithm is total: $\log_2 0=0$, and for a negative argument it equals the base-$2$ logarithm of its absolute value. If $O$ is empty, the value is $0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.observationMutualInfoBits

For any finite type $O$, arbitrary types $A,B$, any function $p:O\to\mathbb R$, and observations $a:O\to A$, $b:O\to B$, this defines

$$\begin{aligned} &-\sum_{o\in O}p(o)\log_2\!\left(\sum_{\substack{t\in O\\a(t)=a(o)}}p(t)\right) -\sum_{o\in O}p(o)\log_2\!\left(\sum_{\substack{t\in O\\b(t)=b(o)}}p(t)\right)\\ &\qquad+\sum_{o\in O}p(o)\log_2\!\left(\sum_{\substack{t\in O\\a(t)=a(o),\ b(t)=b(o)}}p(t)\right). \end{aligned}$$

The weights $p$ may be arbitrary real numbers; they need not form a probability distribution. The observation types need not be finite. The logarithm is total, with $\log_2 0=0$ and $\log_2 x=\log_2|x|$ for $x<0$; an empty $O$ gives value $0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.optimizedReliability

For finite, nonempty alphabets $S,X,Y,Z$, let $W$ specify numbers $w_s(x,y,z)\ge 0$ with $\sum_{x,y,z}w_s(x,y,z)=1$ for every $s\in S$, and let $R_P,R_M$ be arbitrary real numbers. Write $a_s(x,y)=\sum_z w_s(x,y,z)$ and $b_s(y)=\sum_x a_s(x,y)$. For each probability distribution $p:S\to\mathbb R$, meaning $p(s)\ge0$ and $\sum_s p(s)=1$, define

$$\begin{aligned} F_1(p,\rho)&=\rho R_P-\log_2\!\left[ \sum_{s,y}p(s)b_s(y) \left(\sum_x\left(\frac{a_s(x,y)}{b_s(y)}\right)^{1/(1+\rho)}\right)^{1+\rho} \right],\\ F_2(p,\rho)&=\rho(R_P-R_M)-\log_2\!\left[ \sum_{x,y}\left(\sum_s p(s)a_s(x,y)^{1/(1+\rho)}\right)^{1+\rho} \right],\\ F_3(p,\rho)&=\rho(R_P-R_M)-\log_2\!\left[ \sum_y\left(\sum_{s,x}p(s)a_s(x,y)^{1/(1+\rho)}\right)^{1+\rho} \right]. \end{aligned}$$

The declaration defines the extended-real value

$$\sup_{\substack{p:S\to\mathbb R\\p\ge0,\ \sum_s p(s)=1}} \min\!\left\{ \sup_{\rho\in[0,1]}F_1(p,\rho),\ \sup_{\rho\in[0,1]}F_2(p,\rho),\ \sup_{\rho\in[0,1]}F_3(p,\rho) \right\},$$

where each $F_i(p,\rho)$ is embedded into the extended reals before taking its supremum. The three suprema are taken separately. Zero output masses are included: division by zero is interpreted as zero, and the total real logarithm used here has $\log_2 0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.publicKeyLeakage

For finite types $S,X,Y,Z$, a channel $W$ with nonempty alphabets and conditional probability laws $w_s$, and a length-$n$ code $C$ with positive message count $M$, normalized encoder probabilities $e$, public map $f$, and Alice key map $a$, put

$$P(m,s,x,y,z)=\frac1M e(m,s)\prod_{i=0}^{n-1}w_{s_i}(x_i,y_i,z_i),\qquad A(m,s,x,y,z)=a(m,x),\qquad V(m,s,x,y,z)=(z,f(m,x)).$$

For any observation $h$ on this finite tuple space, define its entropy by

$$H_P(h)=-\sum_o P(o)\log_2\!\left(\sum_{t:\,h(t)=h(o)}P(t)\right).$$

The defined leakage is exactly $H_P(A)+H_P(V)-H_P(o\mapsto(A(o),V(o)))$. The logarithm is the total real base-$2$ logarithm, whose value at $0$ is $0$. The definition includes $n=0$, using the empty product $1$.

QAlgorithms.Papers.Independent.Intakethird100.P76.region

For finite nonempty alphabets $S,X,Y,Z$ and a channel $W$ whose nonnegative conditional masses $W_s(x,y,z)$ sum to $1$, this set is the closure in $\mathbb R^3$ of the following triples $(R,E,F)$. All three coordinates are nonnegative, and there exists a code at every length $L=n+1$, with positive finite message, public-message, and key sizes $M_n,P_n,K_n$, stochastic encoder $e_n(m,s^L)$, and deterministic public, Alice-key, and Bob-key maps $a_n(m,x^L)$, $k_n(m,x^L)$, and $b_n(y^L,a)$. Under the sample mass

$$\mu_n(m,s^L,x^L,y^L,z^L) =M_n^{-1}e_n(m,s^L)\prod_iW_{s_i}(x_i,y_i,z_i),$$

let $A_n=k_n(m,x^L)$, $V_n=(z^L,a_n(m,x^L))$, $d_n=\Pr[A_n\ne b_n(y^L,a_n(m,x^L))]$, and $\ell_n=H_{\mu_n}(A_n)+H_{\mu_n}(V_n)-H_{\mu_n}(A_n,V_n)$, using

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right).$$

Fixed nonnegative $r_M,r_P,r_K$ must satisfy $M_n=2^{\lceil Lr_M\rceil}$, $P_n=2^{\lceil Lr_P\rceil}$, and $K_n\le2^{Lr_K}$. For every $\varepsilon>0$, eventually $H_{\mu_n}(A_n)/L\ge R-\varepsilon$, while $E\le\liminf_n g_n(d_n)$ and $F\le\liminf_n g_n(\ell_n)$, where $g_n(0)=+\infty$ and $g_n(t)=-\log_2(t)/(n+1)$ otherwise. No cost constraint is imposed. Taking the closure includes limits of such triples, whether or not the limiting triple itself has such a code sequence.

QAlgorithms.Papers.Independent.Intakethird100.P76.reliabilityExponent

Let $S,X,Y,Z$ be finite nonempty sets, let each $W_s$ be a probability distribution on $X\times Y\times Z$, let $p:S\to\mathbb R$ be arbitrary, and let $R_P,R_M\in\mathbb R$. Define $A_s(x,y)=\sum_zW_s(x,y,z)$ and $B_s(y)=\sum_xA_s(x,y)$, and, for $0\le r\le1$, define the real numbers

$$\begin{aligned} F_1(r)&=rR_P-\log_2\!\left[ \sum_{s,y}p(s)B_s(y) \left(\sum_x\left(\frac{A_s(x,y)}{B_s(y)}\right)^{1/(1+r)}\right)^{1+r} \right],\\ F_2(r)&=r(R_P-R_M)-\log_2\!\left[ \sum_{x,y}\left(\sum_sp(s)A_s(x,y)^{1/(1+r)}\right)^{1+r} \right],\\ F_3(r)&=r(R_P-R_M)-\log_2\!\left[ \sum_y\left(\sum_{s,x}p(s)A_s(x,y)^{1/(1+r)}\right)^{1+r} \right]. \end{aligned}$$

The declaration defines the extended-real value

$$\operatorname{reliabilityExponent}(W,p,R_P,R_M) =\min\left\{\sup_{r\in[0,1]}F_1(r),\, \min\left\{\sup_{r\in[0,1]}F_2(r),\sup_{r\in[0,1]}F_3(r)\right\}\right\},$$

where each real value is embedded in the extended real line before taking its supremum. Each supremum is taken independently and includes both endpoints. No probability-law assumption is imposed on $p$, and no sign restriction is imposed on the rates. Zero marginal probabilities are included using division by zero equal to zero; powers and logarithms are total, with $\log_2 0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.reliabilityOne

For finite nonempty alphabets $S,X,Y,Z$, let $W_s(x,y,z)\ge0$ sum to $1$ over $x,y,z$ for every $s$. For an arbitrary function $p:S\to\mathbb R$ and arbitrary real parameters $\rho,R_P$, put $a_{sxy}=\sum_zW_s(x,y,z)$ and $b_{sy}=\sum_{x,z}W_s(x,y,z)$. The declaration defines the real number

$$\rho R_P-\log_2\!\left( \sum_{s\in S}\sum_{y\in Y} p(s)b_{sy} \left[\sum_{x\in X} \left(\frac{a_{sxy}}{b_{sy}}\right)^{1/(1+\rho)} \right]^{1+\rho} \right).$$

No probability-law assumption is imposed on $p$, and neither real parameter is restricted. All divisions, real powers, and logarithms are total operations: a zero denominator gives quotient $0$, so $\rho=-1$ makes $1/(1+\rho)=0$, and $b_{sy}=0$ makes each displayed ratio $0$; the real-power convention includes $0^0=1$. The logarithm is $\log_2u=\log u/\log2$, where the total real logarithm has $\log0=0$ and $\log u=\log|u|$ for negative $u$.

QAlgorithms.Papers.Independent.Intakethird100.P76.reliabilityThree

Let $S,X,Y,Z$ be finite nonempty sets, and let $W_s(x,y,z)$ be a probability distribution on $X\times Y\times Z$ for every $s\in S$. For any function $p:S\to\mathbb R$ and any real numbers $\rho,R_P,R_M$, write $A_s(x,y)=\sum_{z\in Z}W_s(x,y,z)$. The declaration defines

$$\operatorname{reliabilityThree}(W,p,\rho,R_P,R_M) =\rho(R_P-R_M)-\log_2\!\left[ \sum_{y\in Y} \left(\sum_{s\in S}\sum_{x\in X}p(s)A_s(x,y)^{1/(1+\rho)}\right)^{1+\rho} \right].$$

The function $p$ need not be a probability distribution, and none of the real parameters is restricted. The real powers, reciprocals, and logarithms are total operations, including division by zero and $\log_2 0$ being zero; thus $\rho=-1$ is also an allowed argument.

QAlgorithms.Papers.Independent.Intakethird100.P76.reliabilityTwo

Let $S,X,Y,Z$ be finite nonempty sets, and let $W$ assign to each $s\in S$ a probability distribution $W_s(x,y,z)$ on $X\times Y\times Z$. For an arbitrary function $p:S\to\mathbb R$ and arbitrary real numbers $\rho,R_P,R_M$, put $A_s(x,y)=\sum_{z\in Z}W_s(x,y,z)$. The declaration defines

$$\operatorname{reliabilityTwo}(W,p,\rho,R_P,R_M) =\rho(R_P-R_M)-\log_2\!\left[ \sum_{x\in X}\sum_{y\in Y} \left(\sum_{s\in S}p(s)A_s(x,y)^{1/(1+\rho)}\right)^{1+\rho} \right].$$

There is no assumption that $p$ is nonnegative or normalized, or that the real parameters are nonnegative. Powers and logarithms use their total real-valued definitions; division by zero and $\log_2 0$ equal zero. In particular, $\rho=-1$ is included, with $1/(1+\rho)=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.renyiBits

For any finite type $A$, any function $p:A\to\mathbb R$, and any real parameter $\alpha$, this defines

$$-\frac{\log_2\!\left(\sum_{a\in A}p(a)^{\,1+\alpha}\right)}{\alpha}.$$

Neither nonnegativity nor normalization of $p$ is assumed, and $\alpha$ is unrestricted. Powers use the total real-power operation: for $x>0$, $x^r=\exp(r\log x)$; $0^0=1$, $0^r=0$ for $r\ne0$; and for $x<0$, $x^r=\exp(r\log|x|)\cos(\pi r)$. The logarithm is $0$ at $0$ and uses absolute values at negative arguments. Division by zero gives $0$, so the definition gives $0$ at $\alpha=0$; it also gives $0$ for an empty $A$.

QAlgorithms.Papers.Independent.Intakethird100.P76.residualSourceRate

For finite nonempty alphabets $S,X,Y,Z$, a channel $W$ with nonnegative conditional masses summing to $1$, and any function $p:S\to\mathbb R$, put $\mu(s,x,y,z)=p(s)W_s(x,y,z)$ and write $\mathsf S,\mathsf X,\mathsf Y,\mathsf Z$ for the coordinate observations. Define

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right), \quad H_\mu(A\mid C)=H_\mu(A,C)-H_\mu(C), \quad I_\mu(A;B\mid C)=H_\mu(A\mid C)-H_\mu(A\mid(B,C)).$$

The function returns exactly

$$I_\mu(\mathsf X;\mathsf Y\mid\mathsf S) - I_\mu(\mathsf X;\mathsf Z\mid\mathsf S).$$

No nonnegativity or normalization condition is imposed on $p$; all these finite-sum formulas use the total real logarithm, including $\log_2 0=0$ and $\log_2 t=\log_2|t|$ for $t<0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.secrecyExponent

Let $S,X,Y,Z$ be finite nonempty sets, let $W_s$ be a probability distribution on $X\times Y\times Z$ for each $s$, and let $p:S\to\mathbb R$ and $R_K,R_P,R_M\in\mathbb R$ be arbitrary. Put $C_s(x,z)=\sum_yW_s(x,y,z)$ and $p_Z(z)=\sum_{s,x}p(s)C_s(x,z)$. The declaration defines

$$\operatorname{secrecyExponent}(W,p,R_K,R_P,R_M) =\sup_{0<\alpha\le1} \left\{-\alpha(R_K+R_P-R_M) -\log_2\!\left[ \sum_z \begin{cases} 0,&p_Z(z)=0,\\ \displaystyle\sum_{s,x}p(s)C_s(x,z) \left(\frac{C_s(x,z)}{p_Z(z)}\right)^\alpha,&p_Z(z)\ne0 \end{cases} \right]\right\}.$$

This is a supremum in the extended real line of the displayed real values; $\alpha=0$ is excluded and $\alpha=1$ is included. Neither normalization nor nonnegativity of $p$ is required, and the rates have no sign restrictions. The zero branch is used whenever $p_Z(z)=0$, and real powers and logarithms use their total definitions, including $\log_2 0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.secrecyTrial

Let $S,X,Y,Z$ be finite nonempty sets, and let $W_s(x,y,z)$ be a probability distribution for every $s\in S$. For an arbitrary function $p:S\to\mathbb R$ and arbitrary real numbers $\alpha,R_K,R_P,R_M$, define

$$C_s(x,z)=\sum_yW_s(x,y,z),\qquad p_Z(z)=\sum_{s,x}p(s)C_s(x,z).$$

The declaration defines

$$\operatorname{secrecyTrial}(W,p,\alpha,R_K,R_P,R_M) =-\alpha(R_K+R_P-R_M) -\log_2\!\left[ \sum_z \begin{cases} 0,&p_Z(z)=0,\\ \displaystyle\sum_{s,x}p(s)C_s(x,z) \left(\frac{C_s(x,z)}{p_Z(z)}\right)^\alpha,&p_Z(z)\ne0. \end{cases} \right].$$

There is no assumption that $p$ is a probability distribution or that any parameter is nonnegative. The zero branch depends only on the equality $p_Z(z)=0$, including when that equality results from cancellation among signed terms. Powers and logarithms are total real-valued operations, with $\log_2 0=0$.

QAlgorithms.Papers.Independent.Intakethird100.P76.senderExcitedCapacity

For finite nonempty alphabets $S,X,Y,Z$, a channel $W$ whose $W_s(x,y,z)$ are nonnegative and sum to $1$ for each $s$, an arbitrary function $\mathrm{cost}:S\to\mathbb R$, and an optional real bound $\Gamma$, this is the supremum in the extended real numbers of the real rates $R\ge0$ satisfying the following conditions. There exists a code for every length $L=n+1$, with positive finite message, public-message, and key sizes $M_n,P_n,K_n$, a stochastic encoder $e_n(m,s^L)$, and deterministic public, Alice-key, and Bob-key maps $a_n(m,x^L)$, $k_n(m,x^L)$, and $b_n(y^L,a)$. Samples have mass

$$\mu_n(m,s^L,x^L,y^L,z^L) =M_n^{-1}e_n(m,s^L)\prod_iW_{s_i}(x_i,y_i,z_i).$$

There are fixed $r_M,r_P,r_K\ge0$ with $M_n=2^{\lceil Lr_M\rceil}$, $P_n=2^{\lceil Lr_P\rceil}$, and $K_n\le2^{Lr_K}$. If $\Gamma=g$, every encoder-supported word satisfies $\sum_i\mathrm{cost}(s_i)\le Lg$; an absent $\Gamma$ imposes no cost condition. The probability of unequal Alice and Bob keys tends to zero, the Alice-key entropy per symbol has eventual lower bound $R-\varepsilon$ for every $\varepsilon>0$, and the mutual information between Alice's key and $(z^L,a_n(m,x^L))$, divided by $L$, tends to zero. Here an observation $A$ has entropy

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right),$$

and mutual information is $H_\mu(A)+H_\mu(B)-H_\mu(A,B)$. Length $1$ is included. The supremum need not itself be an admitted rate; the extended-real supremum is $-\infty$ if the rate set is empty and $+\infty$ if it is unbounded above.

QAlgorithms.Papers.Independent.Intakethird100.P76.strongCapacity

For finite nonempty alphabets $S,X,Y,Z$ and a channel $W$ with nonnegative conditional masses $W_s(x,y,z)$ summing to $1$, this is the extended-real supremum of real rates $R\ge0$ for which there exist $E,F>0$ and the following code sequence. At every length $L=n+1$, including length $1$, a code has positive finite message, public-message, and key sizes $M_n,P_n,K_n$, a stochastic encoder $e_n(m,s^L)$, and deterministic public, Alice-key, and Bob-key maps $a_n(m,x^L)$, $k_n(m,x^L)$, and $b_n(y^L,a)$. Under

$$\mu_n(m,s^L,x^L,y^L,z^L) =M_n^{-1}e_n(m,s^L)\prod_iW_{s_i}(x_i,y_i,z_i),$$

write $A_n=k_n(m,x^L)$, $V_n=(z^L,a_n(m,x^L))$, $d_n=\Pr[A_n\ne b_n(y^L,a_n(m,x^L))]$, and $\ell_n=I_{\mu_n}(A_n;V_n)$. Here

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right), \qquad I_\mu(A;B)=H_\mu(A)+H_\mu(B)-H_\mu(A,B).$$

Fixed nonnegative $r_M,r_P,r_K$ must give $M_n=2^{\lceil Lr_M\rceil}$, $P_n=2^{\lceil Lr_P\rceil}$, and $K_n\le2^{Lr_K}$. The entropy per symbol is eventually at least $R-\varepsilon$ for every $\varepsilon>0$, and

$$E\le\liminf_n g_n(d_n),\qquad F\le\liminf_n g_n(\ell_n),$$

where $g_n(0)=+\infty$ and $g_n(t)=-\log_2(t)/(n+1)$ otherwise. There is no cost constraint. The supremum does not require attainment; it is $-\infty$ for an empty rate set and $+\infty$ for an unbounded rate set.

QAlgorithms.Papers.Independent.Intakethird100.P76.transcript

For a finite type $S$, arbitrary types $X,Y,Z$, a natural block length $n$, an interactive code $C$, and a sample $((m,s^n,x^n,y^n,z^n),b)$, where $m$ is a base message index and $b$ a Bob-seed index, the declaration defines a transcript using the code’s natural round count $r$, positive symbol count $d$, sender function, and talk functions. Start with the empty list $t_0=[]$; for each $i=0,\ldots,r-1$, append exactly one symbol according to

$$t_{i+1}= \begin{cases} t_i\mathbin{+\!\!+}[\operatorname{AliceTalk}(m,x^n,t_i)],&\operatorname{sender}(i)=\mathrm{true},\\ t_i\mathbin{+\!\!+}[\operatorname{BobTalk}(b,y^n,t_i)],&\operatorname{sender}(i)=\mathrm{false}. \end{cases}$$

The result is $t_r$, a list of $r$ symbols from $\{0,\ldots,d-1\}$. The words $s^n,z^n$ do not enter this calculation; if $r=0$, the result is the empty list.

QAlgorithms.Papers.Independent.Intakethird100.P76.upperObjective

For finite nonempty alphabets $S,X,Y,Z$, a channel $W$ with nonnegative conditional masses summing to $1$, and any real-valued function $p$ on $S$, put $\mu(s,x,y,z)=p(s)W_s(x,y,z)$ and denote the coordinate observations by $\mathsf S,\mathsf X,\mathsf Y,\mathsf Z$. With

$$H_\mu(A)=-\sum_o\mu(o)\log_2\!\left(\sum_{o':\,A(o')=A(o)}\mu(o')\right),$$

this function is the following difference of conditional-entropy expressions:

$$\bigl[H_\mu((\mathsf X,\mathsf S),\mathsf Z)-H_\mu(\mathsf Z)\bigr] - \bigl[H_\mu((\mathsf X,\mathsf S),(\mathsf Y,\mathsf Z)) -H_\mu(\mathsf Y,\mathsf Z)\bigr].$$

Thus it is the explicitly defined conditional information $I_\mu((\mathsf X,\mathsf S);\mathsf Y\mid\mathsf Z)$. No probability-law assumption is imposed on $p$; the sums use the total real logarithm, including $\log_2 0=0$ and $\log_2 t=\log_2|t|$ for negative $t$.

QAlgorithms.Papers.Independent.Intakethird100.P76.xyMass

For finite nonempty alphabets $S,X,Y,Z$, let $W_s(x,y,z)\ge0$ satisfy $\sum_{x,y,z}W_s(x,y,z)=1$ for every $s$. For every $s\in S$, $x\in X$, and $y\in Y$, this declaration defines the real number

$$W_{XY\mid s}(x,y)=\sum_{z\in Z}W_s(x,y,z).$$

QAlgorithms.Papers.Independent.Intakethird100.P76.xzMass

For finite nonempty alphabets $S,X,Y,Z$, let $W_s(x,y,z)\ge0$ satisfy $\sum_{x,y,z}W_s(x,y,z)=1$ for every $s$. For every $s\in S$, $x\in X$, and $z\in Z$, this declaration defines the real number

$$W_{XZ\mid s}(x,z)=\sum_{y\in Y}W_s(x,y,z).$$

QAlgorithms.Papers.Independent.Intakethird100.P76.yMass

For finite nonempty alphabets $S,X,Y,Z$, let $W_s(x,y,z)\ge0$ satisfy $\sum_{x,y,z}W_s(x,y,z)=1$ for every $s$. For every $s\in S$ and $y\in Y$, this declaration defines the real number

$$W_{Y\mid s}(y)=\sum_{x\in X}\sum_{z\in Z}W_s(x,y,z).$$