Strong-secrecy capacity of a finite DMC wiretap channel

Let $C=C(W)$. A constant $U$ gives value zero, so $C\ge 0$. By [F10] the maximum is attained with finite $\mathrm{\mid }U\mathrm{\mid }\le \mathrm{\mid }X\mathrm{\mid }$, and [F5] makes each mutual information finite, so $C<\mathrm{\infty }$. For any fixed finite $P_{U,X}$, restrict $U$ to its positive-mass values and define the induced Bob and Eve channels $Q_Y(y\mid u):={\sum }_x{P}_{X\mid U}(x\mid u)W_Y(y\mid x),Q_Z(z\mid u):={\sum }_x{P}_{X\mid U}(x\mid u)W_Z(z\mid x)\mathrm{.}$ Each row sums to one because $P_{X\mid U=u}$ and the marginals $W_Y,W_Z$ are stochastic. These induced channels are finite DMCs, and their input-output mutual informations are $I(U;Y)$ and $I(U;Z)$.

Suppose $C>0$ and fix any $0\le R<C$. By [F10], choose a maximizing law $P_{U,X}$. Choose $R^{\mathrm{\prime }}$ with $R<R^{\mathrm{\prime }}<C$, then choose $R_0>I(U;Z)$ so that $R^{\mathrm{\prime }}+R_0<I(U;Y)$. Choose ${\gamma }_Y>0$ with $R^{\mathrm{\prime }}+R_0<I(U;Y)-{\gamma }_Y$. For each $n$, set $M_n=\lceil e^{n{R}^{\mathrm{\prime }}}\rceil$, $L_n=\lceil e^{n{R}_0}\rceil$, and independently draw $M_n{L}_n$ words $U^n(m,l)$ from $P_U^n$.

If $C=0$, the one-message code has zero error and zero leakage at every blocklength, so all four capacities are at least zero. In all cases, strong secrecy implies weak secrecy because [F5] and [F12] give $0\le I(M;Z^n)\mathrm{/}n\le I(M;Z^n)$ for $n\ge 1$; maximal error tending to zero implies average error tending to zero.

For the converse, consider any sequence of wiretap codes with average error $p_n\to 0$ and weak leakage ${\mathrm{\ell }}_n:=I(M;Z^n)$ satisfying ${\mathrm{\ell }}_n\mathrm{/}n\to 0$. Fano's bound [F7] gives $(1-p_n)\ln \mathrm{\mid }{\mathcal{M}}_n\mathrm{\mid }\le I(M;Y^n)+h_2(p_n)=I(M;Y^n)-I(M;Z^n)+{\mathrm{\ell }}_n+h_2(p_n)\mathrm{.}$ The binary entropy is bounded by $\ln 2$, since [F12] applied to $(p_n,1-p_n)$ and $(1\mathrm{/}2,1\mathrm{/}2)$ gives $0\le \ln 2-h_2(p_n)$.

For $i=0,\dots ,n$, set $A_i:=I(M;Y^i,Z_{i+1}^n)$, with empty strings omitted, and set $V_i:=(Y^{i-1},Z_{i+1}^n)$. The mutual-information chain rule [F6] gives $I(M;Y^n)-I(M;Z^n)=A_n-A_0={\sum }_{i=1}^n[I(M;Y_i\mid V_i)-I(M;Z_i\mid V_i)]\mathrm{.}$ Indeed, $A_i-A_{i-1}=I(M;Y_i\mid V_i)-I(M;Z_i\mid V_i)$ for each $i$, and the sum telescopes.

For a selected codebook, encode message $m$ by choosing $l$ uniformly and, conditional on $U^n(m,l)=u^n$, draw $X^n$ according to $P_{X^n\mid U^n}(x^n\mid u^n)={\prod }_{i=1}^n{P}_{X\mid U}(x_i\mid u_i),$ using independent private draws at the coordinates. Thus the induced channels from $U$ to Bob and Eve are the finite DMCs $Q_Y(y\mid u):={\sum }_x{P}_{X\mid U}(x\mid u)W_Y(y\mid x)$ and $Q_Z(z\mid u):={\sum }_x{P}_{X\mid U}(x\mid u)W_Z(z\mid x)$, with block laws $Q_Y^n$ and $Q_Z^n$. For an output with $P_Y^n(y^n)=0$, declare erasure; it has probability zero because every sampled letter has positive $P_U$-mass and $P_Y(y)={\sum }_u{P}_U(u)Q_Y(y\mid u)$. For an output with $P_Y^n(y^n)>0$, assign score $-\mathrm{\infty }$ if $Q_Y^n(y^n\mid u^n)=0$ and otherwise use its log likelihood ratio. Decode the pair $(m,l)$ as the unique codeword satisfying $\ln \frac{Q_Y^n(Y^n\mid U^n(m,l))}{P_Y^n(Y^n)}>n(I(U;Y)-{\gamma }_Y)$; output its message coordinate $m$, and declare erasure if no unique pair passes. Under the transmitted pair, the missed-threshold probability is at most ${\sigma }_Y^2\mathrm{/}(n{\gamma }_Y^2)$ by [F8]. For any incorrect pair, its independently drawn word is independent of the received $Y^n\sim P_Y^n$ under the random-code ensemble, and ${\mathbb{E}}_{U^n}[Q_Y^n(y^n\mid U^n)\mathrm{/}{P}_Y^n(y^n)]=1$ on the support of $P_Y^n$. On the threshold event the likelihood ratio exceeds $e^{n(I(U;Y)-{\gamma }_Y)}$, so its indicator is bounded above by the ratio times $e^{-n(I(U;Y)-{\gamma }_Y)}$; taking expectations bounds the false-alarm probability by that exponential. If the true pair uniquely passes, the message is decoded correctly; hence message error is bounded by the missed-threshold event or the union of false-alarm events. The union bound over at most $M_n{L}_n-1$ incorrect pairs tends to zero: since $R^{\mathrm{\prime }},R_0\ge 0$, $M_n{L}_n\le 4e^{n(R^{\mathrm{\prime }}+R_0)}$, and $R^{\mathrm{\prime }}+R_0<I(U;Y)-{\gamma }_Y$. Thus the ensemble average message error tends to zero.

The code and channel law factor as $P_M(m)P_{X^n\mid M}(x^n\mid m){\prod }_{j=1}^{n}W(y_j,z_j\mid x_j)\mathrm{.}$ In this finite sum, the time-$i$ factor $W(y_i,z_i\mid x_i)$ separates from all other coordinate factors. Therefore, after summing over the other inputs and outputs, $P(Y_i=y,Z_i=z\mid M=m,X_i=x,V_i=v)=W(y,z\mid x)$ whenever the conditioning event has positive probability. This proves $M-X_i-(Y_i,Z_i)$ conditional on each positive-mass $V_i=v$. Thus $P_{M,X_i\mid V_i=v}W$ is a finite auxiliary law allowed in the maximum defining $C$. By [F10], $I(M;Y_i\mid V_i=v)-I(M;Z_i\mid V_i=v)\le C\mathrm{.}$ Average over positive-mass $v$ and sum over $i$ in step 1.5 to obtain $I(M;Y^n)-I(M;Z^n)\le nC$.

Use the same conditional product encoder law $P_{X^n\mid U^n}(x^n\mid u^n)={\prod }_{i=1}^n{P}_{X\mid U}(x_i\mid u_i)$ with independent private coordinate draws as in step 2.1. Summing over $X^n$ through the product wiretap kernel gives the induced Eve DMC block law $Q_Z^n(z^n\mid u^n)={\prod }_{i=1}^n{Q}_Z(z_i\mid u_i)$, where $Q_Z(z\mid u)={\sum }_x{P}_{X\mid U}(x\mid u)W_Z(z\mid x)$. Eve's conditional output law for message $m$ is the mixture of the $L_n$ induced $Q_Z^n(\cdot \mid U^n(m,l))$ outputs. Let $d(\mathcal{C})$ be the average over $m$ of its KL divergence from $P_Z^n$. For each fixed $m$, its randomization subcode has exactly the IID codebook law in [F9], so ${\mathbb{E}}_{\mathcal{C}}d(\mathcal{C})\to 0$. Let $a(\mathcal{C})$ be the codebook's average Bob error. Step 2.1 and finite averaging give ${\mathbb{E}}_{\mathcal{C}}a(\mathcal{C})\to 0$. Fix an ordering of the finite auxiliary alphabet and order its finite word/codebook sets lexicographically. At each $n$, take the first codebook whose $a({\mathcal{C}}_n)+d({\mathcal{C}}_n)$ is no larger than its finite ensemble mean. Such a codebook exists by finite averaging, so this specifies a sequence with $a({\mathcal{C}}_n)+d({\mathcal{C}}_n)\to 0$ without countable choices.

Write ${\eta }_n=a({\mathcal{C}}_n)+d({\mathcal{C}}_n)$ and, for each message $m$, write $e_m$ for its Bob error and $d_m=D(P_{Z^n\mid m,{\mathcal{C}}_n}\mathrm{\parallel }{P}_Z^n)$. Delete every message with $e_m>t_n$ or $d_m>t_n$, where $t_n=\sqrt{{\eta }_n}+1\mathrm{/}n$. For each message, $\mathbf{1}\{e_m>t_n\text{ or }{d}_m>t_n\}\le (e_m+d_m)\mathrm{/}{t}_n$; averaging over the uniform message bounds the deleted fraction by ${\eta }_n\mathrm{/}{t}_n\le \sqrt{{\eta }_n}$. Thus for all sufficiently large $n$ the retained fraction tends to one and is positive, and each retained message has both $e_m,d_m\le t_n\to 0$. Restrict the encoder to retained messages and map any old decoder output outside the retained set to erasure; this cannot increase the error for a retained message. For the finitely many earlier blocklengths use a one-message code.

For the uniform message on the retained set $S_n$, put ${\bar{P}}_{Z^n}=\mathrm{\mid }{S}_n{\mathrm{\mid }}^{-1}{\sum }_{m\in S_n}{P}_{Z^n\mid m,{\mathcal{C}}_n}$. Expanding the finite KL sums and grouping terms gives the exact identity $\frac{1}{\mathrm{\mid }{S}_n\mathrm{\mid }}{\sum }_{m\in S_n}D(P_{Z^n\mid m,{\mathcal{C}}_n}\mathrm{\parallel }{P}_Z^n)=\frac{1}{\mathrm{\mid }{S}_n\mathrm{\mid }}{\sum }_{m,z^n:P_{Z^n\mid m,{\mathcal{C}}_n}(z^n)>0}{P}_{Z^n\mid m,{\mathcal{C}}_n}(z^n)\ln \frac{P_{Z^n\mid m,{\mathcal{C}}_n}(z^n)}{P_Z^n(z^n)}=\frac{1}{\mathrm{\mid }{S}_n\mathrm{\mid }}{\sum }_{m,z^n:P_{Z^n\mid m,{\mathcal{C}}_n}(z^n)>0}{P}_{Z^n\mid m,{\mathcal{C}}_n}(z^n)\ln \frac{P_{Z^n\mid m,{\mathcal{C}}_n}(z^n)}{{\bar{P}}_{Z^n}(z^n)}+{\sum }_{z^n:{\bar{P}}_{Z^n}(z^n)>0}{\bar{P}}_{Z^n}(z^n)\ln \frac{{\bar{P}}_{Z^n}(z^n)}{P_Z^n(z^n)}=I(M;Z^n)+D({\bar{P}}_{Z^n}\mathrm{\parallel }{P}_Z^n)\mathrm{.}$ The reference law has positive mass wherever any induced Eve output has positive mass, so all terms are finite. By [F12], $I(M;Z^n)\le \mathrm{\mid }{S}_n{\mathrm{\mid }}^{-1}{\sum }_{m\in S_n}{d}_m\le t_n\to 0$. Also $\mathrm{\mid }{S}_n\mathrm{\mid }\ge (1-\sqrt{{\eta }_n})M_n$ and $M_n\ge e^{n{R}^{\mathrm{\prime }}}$, while $n^{-1}\ln (1-\sqrt{{\eta }_n})\to 0$; hence ${\mathrm{lim\hspace{0.17em}inf}}_n{n}^{-1}\ln \mathrm{\mid }{S}_n\mathrm{\mid }\ge R^{\mathrm{\prime }}$. This constructs a maximal-error, strong-secrecy sequence at rate at least $R^{\mathrm{\prime }}$, and therefore every $R<C$ is achievable for all four criteria.

Substitute step 2.2 into step 1.4, divide by $n(1-p_n)$, and use $p_n\to 0$, ${\mathrm{\ell }}_n\mathrm{/}n\to 0$, and $0\le h_2(p_n)\le \ln 2$ to get ${\mathrm{lim\hspace{0.17em}sup}}_n{n}^{-1}\ln \mathrm{\mid }{\mathcal{M}}_n\mathrm{\mid }\le C$. This converse applies to weak secrecy and average error; it also bounds strong-secrecy or maximal-error sequences because each implies the corresponding weaker condition. Together with the achievability and zero-capacity branches, all four operational capacities equal $C(W)$.