Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 8 results · all verified · 0 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 8 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Secrecy and Information Privacy

1 · Prerequisites

2 · Summary

All alphabets and probability laws on this page are finite, and information is measured in natural-log nats as in Information units and logarithm-base convention. A wiretap channel has one input and two outputs whose conditional dependence is retained in the joint kernel:

\begin{tikzcd}
& Y \\
X \arrow[ur, "W_Y"] \arrow[dr, "W_Z"'] & \\
& Z
\end{tikzcd}

The two arrows label the Bob and Eve marginals of the joint law $W (y, z ∣ x)$ . They do not assert that $Y$ and $Z$ are conditionally independent given $X$ . The block law is the coordinate product of this joint kernel. A code uses a uniform message, private encoder randomness and no feedback or preshared secret key; its public description is available to Eve.

Information leakage and equivocation are defined in Information leakage and equivocation for finite observations. Weak secrecy requires $I (M; Z^{n}) / n \to 0$ , while strong secrecy requires $I (M; Z^{n}) \to 0$ , as in Weak and strong secrecy for wiretap code sequences. Strong secrecy implies weak secrecy, but the converse fails; the companion page gives a noiseless example. Capacity here is defined operationally for both average and maximal error, and for both secrecy criteria. The local finite information-density lemma supports fixed-auxiliary threshold decoding, while the resolvability lemma makes Eve's induced output law approach a product target in expected KL and total variation. The capacity theorem proves the same auxiliary formula for all four capacities:

$\max_{P_{U, X} : U - X - (Y, Z)} [I (U; Y) - I (U; Z)], ∣ U ∣ \leq ∣ X ∣ .$

For a degraded channel in the sense of Finite degraded wiretap channel, Eve's output is generated from Bob's by a finite stochastic kernel, the auxiliary reduces to $U = X$ , and the formula becomes $\max_{P_{X}} [I (X; Y) - I (X; Z)]$ .

For finite source privacy in Finite-source privacy–utility region, a release kernel gives the factorization $P_{S X Z} = P_{S X} K_{Z ∣ X}$ :

\begin{tikzcd}
S \arrow[r] & X \arrow[r, "K"] & Z
\end{tikzcd}

The privacy–utility coordinates are $(I (S; Z), I (X; Z))$ : the first measures leakage about sensitive data and the second measures retained information about useful data. Perfect privacy is exactly equality of the conditional output laws across positive-support sensitive values, by A finite kernel criterion for perfect privacy. This criterion is a kernel condition and does not impose a distortion or rate constraint.

Universal hashing is treated separately by Classical leftover-hash bound with public side information as a total-variation guarantee with the public seed included alongside Eve's side information. For conditional guessing probability $g (X ∣ Z)$ and an $M$ -valued two-universal hash, the bound is $TV \leq \frac{1}{2} \sqrt{M g (X ∣ Z)}$ ; in particular, $M g (X ∣ Z) \leq 4 ε^{2}$ guarantees distance at most $ε$ . This bound does not by itself state an unnormalized mutual-information guarantee.

3 · Logical flowchart

4 · Definitions, theorems and proofs

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Classical leftover-hash bound with public side information

Statement

Let $X, Z$ be finite random variables with joint law $P_{X Z}$ . Let $M \geq 1$ be an integer and let $H$ be a finite nonempty family of functions $h : X \to [M]$ . Choose $H$ uniformly from $H$ independently of $(X, Z)$ , and assume the family is two-universal:

$\Pr_{H} [h_{H} (x) = h_{H} (x^{'})] \leq \frac{1}{M} for every x \neq x^{'} .$

Set $K : = h_{H} (X)$ ; the seed $H$ is public. Define the conditional guessing probability

$g (X ∣ Z) : = \sum_{z} \max_{x} P_{X Z} (x, z),$

with zero-mass $z$ contributing zero, and define total variation by $TV (P, Q) : = \frac{1}{2} \sum ∣ P - Q ∣$ on the common finite alphabet. Then

$TV (P_{K H Z}, U_{M} \otimes P_{H Z}) \leq \frac{1}{2} \sqrt{M g (X ∣ Z)},$

where $U_{M}$ is uniform on $[M]$ . In particular, if $0 < ε \leq \frac{1}{2}$ and $M g (X ∣ Z) \leq 4 ε^{2}$ , then the displayed total-variation distance is at most $ε$ . This is a total-variation guarantee with the seed included in Eve's side information; it is not by itself an unnormalized mutual-information claim.

Facts & Assumptions

Given: A finite joint law $P_{X Z}$ , a finite hash family $H$ , and an independent uniform seed $H$ satisfying the two-universality condition in the Statement.

[A1]

For every distinct $x, x^{'}$ , $\Pr_{H} [h_{H} (x) = h_{H} (x^{'})] \leq 1 / M$ ; this is the two-universality hypothesis stated above.

[A2]

$P_{K H Z}$ is the joint law induced by $K = h_{H} (X)$ and the public seed $H$ ; the comparison law uses the same marginal $P_{H Z}$ and an independent uniform output in $[M]$ .

Proof

1.1A1A2givenalgebra

Fix $z$ with $P_{Z} (z) > 0$ and write $q_{z} (x) : = P (X = x ∣ Z = z)$ and $r_{h, z} (k) : = \sum_{x : h (x) = k} q_{z} (x)$ . Expanding the square and applying [A1] to the off-diagonal terms gives $E_{H} \sum_{k = 1}^{M} r_{H, z} (k)^{2} \leq \sum_{x} q_{z} (x)^{2} + \frac{1}{M} \sum_{x \neq x^{'}} q_{z} (x) q_{z} (x^{'}) = \frac{1}{M} + (1 - \frac{1}{M}) \sum_{x} q_{z} (x)^{2} .$ Since $\sum_{k} r_{h, z} (k) = 1$ , subtracting $1 / M$ from this inequality yields $E_{H} \sum_{k} (r_{H, z} (k) - 1 / M)^{2} \leq \sum_{x} q_{z} (x)^{2}$ .

2.1A2step 1.1givenalgebra

The total-variation definition and [A2] give $TV (P_{K H Z}, U_{M} \otimes P_{H Z}) = \frac{1}{2} \sum_{h, z} P_{H} (h) P_{Z} (z) \sum_{k} ∣ r_{h, z} (k) - 1 / M ∣ .$ For any real vector $(a_{k})_{k = 1}^{M}$ , $M \sum_{k} a_{k}^{2} - (\sum_{k} ∣ a_{k} ∣)^{2} = \sum_{i < j} (∣ a_{i} ∣ - ∣ a_{j} ∣)^{2} \geq 0$ . Applying this identity to $a_{k} = r_{h, z} (k) - 1 / M$ bounds the inner sum by $\sqrt{M \sum_{k} (r_{h, z} (k) - 1 / M)^{2}}$ . For a nonnegative finite random variable $V$ , $E [V] - (E \sqrt{V})^{2} = E [(\sqrt{V} - E \sqrt{V})^{2}] \geq 0$ . Applying this to the squared-bin sum over $(H, Z)$ , followed by step 1.1, gives $TV (P_{K H Z}, U_{M} \otimes P_{H Z}) \leq \frac{1}{2} \sqrt{M \sum_{z} P_{Z} (z) \sum_{x} q_{z} (x)^{2}} .$

3.1A2step 2.1givenalgebra

For every probability vector $q_{z}$ , $\sum_{x} q_{z} (x)^{2} \leq \max_{x} q_{z} (x) \sum_{x} q_{z} (x) = \max_{x} q_{z} (x)$ . Hence $\sum_{z} P_{Z} (z) \sum_{x} q_{z} (x)^{2} \leq \sum_{z} P_{Z} (z) \max_{x} q_{z} (x) = \sum_{z} \max_{x} P_{X Z} (x, z) = g (X ∣ Z) .$ Combining with step 2.1 proves the bound, including zero-mass $z$ by omission.

4.1step 3.1givenalgebra∎

If $M g (X ∣ Z) \leq 4 ε^{2}$ , the bound proved in step 3.1 is at most $ε$ by taking nonnegative square roots.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite-source privacy–utility region

Definition

Let $S$ be a finite sensitive variable and $X$ a finite useful variable with joint law $P_{S X}$ . For each finite nonempty release alphabet $Z$ , choose a stochastic kernel $K (z ∣ x)$ from $X$ to $Z$ (Finite stochastic kernels) and form

$P_{S X Z} (s, x, z) : = P_{S X} (s, x) K (z ∣ x) .$

Thus the induced variables satisfy the explicitly defined factorization $P_{S X Z} = P_{S X} K_{Z ∣ X}$ , written $S - X - Z$ . The privacy–utility region for this source is the closure in $R^{2}$ of

$⋃_{Z, K} {(I (S; Z), I (X; Z))},$

where mutual information uses nats and the finite definition Finite mutual information. The first coordinate is the chosen leakage metric and the second is the chosen retained-information utility. This model does not itself impose a distortion, rate, or perfect-privacy constraint; those define different optimization problems.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Information leakage and equivocation for finite observations

Definition

For finite random variables $M, Z$ , information leakage is the finite mutual information $I (M; Z)$ in nats, as defined in Finite mutual information, and equivocation is the finite conditional entropy $H (M ∣ Z)$ , as defined in Finite conditional entropy. For an $n$ -use code with Eve's observation $Z^{n}$ , its normalized leakage is $n^{- 1} I (M; Z^{n})$ . When $M$ is uniform on a finite message set $M$ , its entropy is $H (M) = \ln ∣ M ∣$ . Zero-probability symbols are handled by the finite entropy and KL conventions cited above.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

The finite wiretap product law is stochastic

Statement

Use one-based coordinate labels for blocks: for $a^{n} \in A^{n}$ , a function on ${0, \dots, n - 1}$ , write $a_{i} : = a^{n} (i - 1)$ for $1 \leq i \leq n$ .

For finite nonempty alphabets $X, Y, Z$ , a stochastic kernel $W (y, z ∣ x)$ from $X$ to $Y \times Z$ , and every $n \geq 1$ , the block formula

$W^{n} (y^{n}, z^{n} ∣ x^{n}) : = \prod_{i = 1}^{n} W (y_{i}, z_{i} ∣ x_{i})$

is a stochastic kernel from $X^{n}$ to $(Y \times Z)^{n}$ .

Facts & Assumptions

Given: A finite stochastic kernel $W (y, z ∣ x)$ between the finite nonempty alphabets above and an integer $n \geq 1$ .

[F1]

Finite stochastic kernels: a finite stochastic kernel has nonnegative entries and each input row sums to one.

Proof

1.1givenF1

Fix $x^{n} \in X^{n}$ . Every factor $W (y_{i}, z_{i} ∣ x_{i})$ is nonnegative by [F1], so every product $W^{n} (y^{n}, z^{n} ∣ x^{n})$ is nonnegative.

2.1F1step 1.1algebra∎

Finite distributivity factors the output sum as $\sum_{y^{n}, z^{n}} W^{n} (y^{n}, z^{n} ∣ x^{n}) = \prod_{i = 1}^{n} (\sum_{y_{i}, z_{i}} W (y_{i}, z_{i} ∣ x_{i})) = \prod_{i = 1}^{n} 1 = 1.$ The row sums are one by [F1]; together with step 1.1 these are exactly the stochastic-kernel conditions.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite discrete memoryless wiretap channel and code model

Definition

Let $X, Y, Z$ be finite nonempty alphabets and let $W (y, z ∣ x)$ be a stochastic kernel from $X$ to $Y \times Z$ (Finite stochastic kernels). Its Bob and Eve marginals are $W_{Y} (y ∣ x) : = \sum_{z} W (y, z ∣ x)$ and $W_{Z} (z ∣ x) : = \sum_{y} W (y, z ∣ x)$ ; each is a finite DMC in the sense of Finite discrete memoryless channels.

For each integer $n \geq 1$ , use one-based coordinate labels for blocks: for $a^{n} \in A^{n}$ , a function on ${0, \dots, n - 1}$ , write $a_{i} : = a^{n} (i - 1)$ for $1 \leq i \leq n$ . With these labels, the joint channel law is

$W^{n} (y^{n}, z^{n} ∣ x^{n}) : = \prod_{i = 1}^{n} W (y_{i}, z_{i} ∣ x_{i}) .$

The product formula is a stochastic kernel by The finite wiretap product law is stochastic. Finite distributivity gives $\sum_{z^{n}} W^{n} (y^{n}, z^{n} ∣ x^{n}) = \prod_{i} \sum_{z_{i}} W (y_{i}, z_{i} ∣ x_{i}) = \prod_{i} W_{Y} (y_{i} ∣ x_{i}) = W_{Y}^{n} (y^{n} ∣ x^{n})$ , and the analogous finite sum over $y^{n}$ gives marginal $W_{Z}^{n}$ . The pair $(Y^{n}, Z^{n})$ may be correlated conditional on $X^{n}$ ; neither marginal changes if that coupling changes while the two marginal channels stay fixed.

An $(n, M_{n})$ wiretap code has a finite message set $M_{n}$ , a uniform message $M_{n}$ , a stochastic encoder $P_{X^{n} ∣ M_{n}}$ using private randomness independent of channel noise, and a decoder ${\hat{M}}_{n} : Y^{n} \to M_{n} \cup {e}$ , where $e \notin M_{n}$ denotes erasure and is counted as error. The encoder uses no feedback and the parties have no preshared secret key or forward public aid. The public code description is known to Eve, who observes $Z^{n}$ . Average error is $P_{e, a v}^{(n)} : = \Pr [{\hat{M}}_{n} (Y^{n}) \neq M_{n}]$ ; maximal error is $P_{e, m a x}^{(n)} : = \max_{m \in M_{n}} \Pr [{\hat{M}}_{n} (Y^{n}) \neq m ∣ M_{n} = m]$ . The rate is $n^{- 1} \ln ∣ M_{n} ∣$ nats per channel use. A secrecy metric is specified separately.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

A finite kernel criterion for perfect privacy

Statement

Let $(S, X)$ have a finite joint law and let $K (z ∣ x)$ be a finite release kernel, giving $P_{S X Z} = P_{S X} K_{Z ∣ X}$ as in Finite-source privacy–utility region. Then $I (S; Z) = 0$ if and only if, for each $z$ with $P_{Z} (z) > 0$ , the conditional mixture

$\sum_{x} P_{X ∣ S = s} (x) K (z ∣ x)$

is independent of $s$ over $supp P_{S}$ . No full-support assumption is imposed; zero-mass values of $s$ are not constrained.

Facts & Assumptions

Given: A finite joint law $P_{S X}$ and a finite stochastic release kernel $K (z ∣ x)$ .

[F1]

Finite-source privacy–utility region: $P_{S X Z} (s, x, z) = P_{S X} (s, x) K (z ∣ x)$ , so $P_{Z ∣ S = s} (z) = \sum_{x} P_{X ∣ S = s} (x) K (z ∣ x)$ for $P_{S} (s) > 0$ .

[F2]

Finite mutual information: $I (S; Z) = D (P_{S Z} ∥ P_{S} \otimes P_{Z})$ .

[F3]

Finite KL divergence is nonnegative with equality exactly at equal laws: $D (P ∥ Q) = 0$ if and only if the finite probability vectors $P, Q$ are equal; a positive numerator above a zero denominator gives $+ \infty$ .

Proof

1.1F1F2F3givenalgebra

If $I (S; Z) = 0$ , [F2] and [F3] give $P_{S Z} = P_{S} \otimes P_{Z}$ . For every $s$ with $P_{S} (s) > 0$ , divide the equality $P_{S Z} (s, z) = P_{S} (s) P_{Z} (z)$ by $P_{S} (s)$ and use [F1]. The conditional mixture in the Statement is therefore $P_{Z} (z)$ , independent of $s$ for every $z$ , in particular for every positive-mass $z$ .

1.2F1givenalgebra

Conversely, assume the stated mixture is a constant $c_{z}$ in $s$ on $supp P_{S}$ for each $z$ with $P_{Z} (z) > 0$ . Averaging it over $P_{S}$ shows $c_{z} = P_{Z} (z)$ . If $P_{Z} (z) = 0$ , [F1] gives $0 = P_{Z} (z) = \sum_{s : P_{S} (s) > 0} P_{S} (s) P_{Z ∣ S = s} (z)$ , a finite sum of nonnegative terms with positive weights; hence each $P_{Z ∣ S = s} (z) = 0 = P_{Z} (z)$ . Thus for every $s$ in the support and every $z$ , $P_{Z ∣ S = s} (z) = P_{Z} (z)$ , so [F1] yields $P_{S Z} = P_{S} \otimes P_{Z}$ .

2.1F2F3step 1.2∎

Applying [F2] and [F3] to this equality gives $I (S; Z) = 0$ . This proves both directions, including zero-probability release symbols.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Finite degraded wiretap channel

Definition

A finite wiretap channel Finite discrete memoryless wiretap channel and code model is degraded from Bob to Eve if there is a finite stochastic kernel $V (z ∣ y)$ from Bob's output alphabet to Eve's output alphabet such that

$W (y, z ∣ x) = W_{Y} (y ∣ x) V (z ∣ y) for every x, y, z .$

Equivalently, for every input law $P_{X}$ , the induced joint law is $P_{X} (x) W_{Y} (y ∣ x) V (z ∣ y)$ . The requirement specifies the joint coupling of Bob's and Eve's outputs, not only their separate marginal channels.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Weak and strong secrecy for wiretap code sequences

Definition

Consider a sequence of finite wiretap codes from Finite discrete memoryless wiretap channel and code model, with uniform message $M_{n}$ and Eve's observation $Z^{n}$ . Call it reliable when its average error tends to zero; maximal reliability is the stronger condition that its maximal error tends to zero. Among reliable sequences, weak secrecy means

$\frac{1}{n} I (M_{n}; Z^{n}) ⟶ 0,$

and strong secrecy means

$I (M_{n}; Z^{n}) ⟶ 0,$

where leakage is the unnormalized finite mutual information of Information leakage and equivocation for finite observations and all quantities are in nats. Exact independence at every blocklength, total-variation secrecy, and per-message secrecy are separate conditions and are not identified with either limit here.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Information-density concentration for a fixed finite DMC input law

Statement

Let $W (y ∣ u)$ be a finite DMC and let $P_{U}$ be any fixed input probability vector. Let $P_{Y} (y) = \sum_{u} P_{U} (u) W (y ∣ u)$ . On the joint support $P_{U} (u) W (y ∣ u) > 0$ , define

$J (u, y) : = \ln \frac{W (y ∣ u)}{P_{Y} (y)}, I : = I (U; Y), σ^{2} : = \sum_{u, y : P_{U} (u) W (y ∣ u) > 0} P_{U} (u) W (y ∣ u) (J (u, y) - I)^{2} .$

For IID pairs $(U_{i}, Y_{i}) \sim P_{U} W$ , write $S_{n} = \sum_{i = 1}^{n} J (U_{i}, Y_{i})$ and $B : = \max (0, \max_{P_{U} (u) W (y ∣ u) > 0} J (u, y))$ . Then $J$ is bounded and $E [J] = I$ . For every $δ > 0$ ,

$\Pr [∣ \frac{S_{n}}{n} - I ∣ \geq δ] \leq \frac{σ^{2}}{n δ^{2}} .$

For every $γ > 0$ there is a $ρ \in (0, 1)$ , depending only on $(P_{U}, W, γ)$ , such that

$\Pr [S_{n} > n (I + γ)] \leq ρ^{n} .$

Facts & Assumptions

Given: For each blocklength $n$ , the joint law is $P_{U^{n}, Y^{n}} (u^{n}, y^{n}) = \prod_{i = 1}^{n} P_{U} (u_{i}) W (y_{i} ∣ u_{i})$ for a finite DMC $W$ and input probability vector $P_{U}$ .

[F1]

Finite discrete memoryless channels: for the input word $u^{n}$ , the output law is $W^{n} (y^{n} ∣ u^{n}) = \prod_{i = 1}^{n} W (y_{i} ∣ u_{i})$ .

[F2]

Finite mutual information: $I (U; Y) = \sum_{u, y : P_{U} (u) W (y ∣ u) > 0} P_{U} (u) W (y ∣ u) \ln \frac{W (y ∣ u)}{P_{Y} (y)}$ .

[F3]

Information units and logarithm-base convention: unmarked logarithms are natural, so the information quantities are in nats.

[F4]

The natural logarithm as the inverse of the exponential function: $e^{t}$ is the exponential whose inverse on $(0, \infty)$ is the natural logarithm.

[F5]

The exponential function is smooth and $(\exp)^{'} = \exp$ : the real exponential is differentiable with derivative itself, so a finite sum of exponential functions may be differentiated term by term.

Proof

1.1givenF1F3construct

If $P_{U} (u) W (y ∣ u) > 0$ , then $P_{Y} (y) \geq P_{U} (u) W (y ∣ u) > 0$ . Hence every displayed logarithm is finite; because the joint support is finite, $J$ is bounded and $B < \infty$ . The unmarked logarithm uses nats by [F3].

2.1F1F2givenstep 1.1algebra

The expectation $E [J (U, Y)]$ is the finite sum in [F2], so it equals $I$ . Independence and the common product law in [F1] give $E [S_{n}] = n I$ and $E [(S_{n} - n I)^{2}] = n σ^{2}$ : the cross terms vanish because each centered summand has mean zero, and each diagonal term has second moment $σ^{2}$ . For the nonnegative variable $(S_{n} - n I)^{2}$ , the pointwise inequality $1 {(S_{n} - n I)^{2} \geq n^{2} δ^{2}} \leq (S_{n} - n I)^{2} / (n^{2} δ^{2})$ gives the Chebyshev bound after taking expectations.

3.1F4F5step 2.1choosealgebra

Fix $γ > 0$ and define $ϕ (t) : = E [e^{t (J - I - γ)}]$ . Finite support makes $ϕ$ differentiable at zero, with $ϕ (0) = 1$ and $ϕ^{'} (0) = E [J - I - γ] = - γ < 0$ . By the definition of derivative, some sufficiently small $t > 0$ has $0 < ρ : = ϕ (t) < 1$ .

4.1step 3.1algebra∎

The event $S_{n} > n (I + γ)$ implies $e^{t \sum_{i} (J (U_{i}, Y_{i}) - I - γ)} > 1$ . Its indicator is therefore at most that nonnegative exponential. Independence of the IID pairs gives $\Pr [S_{n} > n (I + γ)] \leq E [e^{t \sum_{i} (J (U_{i}, Y_{i}) - I - γ)}] = ϕ (t)^{n} = ρ^{n} .$ This proves the exponential tail.

DefinitionDefinition: Literature-sourcedProof: Not applicableOpen item page →

Operational weak and strong secrecy capacities

Definition

Fix an error criterion $e \in {a v, m a x}$ and a secrecy criterion $s \in {w e a k, s t r o n g}$ . For each code let $P_{e r r}^{(n)} = P_{e, a v}^{(n)}$ when $e = a v$ and $P_{e r r}^{(n)} = P_{e, m a x}^{(n)}$ when $e = m a x$ . A rate $R \geq 0$ in nats per channel use is $(e, s)$ -achievable for a finite wiretap channel Finite discrete memoryless wiretap channel and code model if there is a sequence of wiretap codes, one at each blocklength $n \geq 1$ , such that

${lim inf}_{n \to \infty} \frac{1}{n} \ln ∣ M_{n} ∣ \geq R, P_{e r r}^{(n)} ⟶ 0,$

and the sequence satisfies secrecy criterion $s$ from Weak and strong secrecy for wiretap code sequences, with leakage measured by Information leakage and equivocation for finite observations. Define $C_{e, s}$ as the supremum of all such rates. Thus this definition gives four operational capacities, distinguished by average or maximal error and weak or strong secrecy.

LemmaStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Finite DMC resolvability by random codebooks

Statement

Let $W (z ∣ u)$ be a finite DMC, let $P_{U}$ be an input probability vector, and let $P_{Z} (z) = \sum_{u} P_{U} (u) W (z ∣ u)$ . On the joint support define $J (u, z) : = \ln (W (z ∣ u) / P_{Z} (z))$ and let $I = I (U; Z)$ . Set $B = \max (0, \max_{P_{U} (u) W (z ∣ u) > 0} J (u, z))$ . For $R_{0} > I$ and any $γ$ with $0 < γ < R_{0} - I$ , draw $L_{n} = ⌈ e^{n R_{0}} ⌉$ independent words $U^{n} (ℓ) \sim P_{U}^{n}$ and define the induced mixture

$P_{Z}^{n} (z^{n}) : = \prod_{i = 1}^{n} P_{Z} (z_{i}), Q_{Z^{n} ∣ C} : = \frac{1}{L_{n}} \sum_{ℓ = 1}^{L_{n}} W^{n} (\cdot ∣ U^{n} (ℓ)) .$

There is a $ρ \in (0, 1)$ , depending only on $(P_{U}, W, γ)$ , for which

$E_{C} D (Q_{Z^{n} ∣ C} ∥ P_{Z}^{n}) \leq e^{- n (R_{0} - I - γ)} + (\ln 2 + n B) ρ^{n},$

and

$E_{C} TV (Q_{Z^{n} ∣ C}, P_{Z}^{n}) \leq ρ^{n} + \frac{1}{2} e^{- n (R_{0} - I - γ) / 2},$

where $TV (P, Q) : = \frac{1}{2} \sum_{z} ∣ P (z) - Q (z) ∣$ . Thus both expected deviations tend to zero. Here $D$ is the directional finite KL divergence of Finite distributions, entropy, divergence, and stochastic matrices.

Facts & Assumptions

Given: A finite DMC $W$ , an input law $P_{U}$ , a rate $R_{0} > I (U; Z)$ , and $0 < γ < R_{0} - I (U; Z)$ .

[F1]

Finite discrete memoryless channels: $W^{n} (z^{n} ∣ u^{n}) = \prod_{i} W (z_{i} ∣ u_{i})$ .

[F2]

The DMC product laws are stochastic kernels: each block product law is a stochastic kernel.

[F3]

Finite mutual information: $I (U; Z) = E [J (U, Z)]$ under $P_{U} W$ .

[F4]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite KL divergence is nonnegative.

[F5]

Information-density concentration for a fixed finite DMC input law: for IID $(U_{i}, Z_{i}) \sim P_{U} W$ , $S_{n} = \sum_{i} J (U_{i}, Z_{i})$ has upper tail $\Pr [S_{n} > n (I + γ)] \leq ρ^{n}$ for some $0 < ρ < 1$ .

[F6]

Information units and logarithm-base convention: unmarked logarithms are natural, so the displayed KL divergence and rates use nats.

[F7]

Finite distributions, entropy, divergence, and stochastic matrices: finite KL is $D (P ∥ Q) = \sum_{p_{i} > 0} p_{i} \ln (p_{i} / q_{i})$ , with value $+ \infty$ if $p_{i} > 0 = q_{i}$ for some coordinate.

[F8]

The natural logarithm is bounded above by its positive argument minus one: for $x \geq 0$ , $\ln (1 + x) \leq x$ .

Proof

1.1givenF1F2F7

Write $Q_{C}$ for the mixture in the Statement. Any $z^{n}$ with $Q_{C} (z^{n}) > 0$ has $P_{Z}^{n} (z^{n}) > 0$ , since each sampled codeword has letters in $supp P_{U}$ and any output reachable from such a letter has positive $P_{Z}$ mass. Hence all divergences below are well-defined and finite.

1.2F1F2F3F5given

For the total-variation bound, let $L_{ℓ} (z^{n}) : = W^{n} (z^{n} ∣ U^{n} (ℓ)) / P_{Z}^{n} (z^{n})$ on the support, let $L_{C} = L_{n}^{- 1} \sum_{ℓ} L_{ℓ}$ , set $T = e^{n (I + γ)}$ , and truncate to ${\tilde{L}}_{ℓ} = L_{ℓ} 1 {L_{ℓ} \leq T}$ and ${\tilde{L}}_{C} = L_{n}^{- 1} \sum_{ℓ} {\tilde{L}}_{ℓ}$ . If $α_{n} : = \Pr [S_{n} > n (I + γ)]$ , then the expected removed mass $\sum_{z^{n}} P_{Z}^{n} (z^{n}) E_{C} [L_{C} - {\tilde{L}}_{C}]$ is exactly $α_{n}$ , and the missing mass $\sum_{z^{n}} P_{Z}^{n} (z^{n}) (1 - E_{C} {\tilde{L}}_{C})$ is also $α_{n}$ , because $\sum_{z^{n}} P_{Z}^{n} (z^{n}) E_{C} L_{C} = 1$ . Since $L_{C} \geq {\tilde{L}}_{C}$ and $E_{C} {\tilde{L}}_{C} \leq 1$ , the triangle inequality gives $2 TV (Q_{C}, P_{Z}^{n}) \leq \sum_{z^{n}} P_{Z}^{n} (z^{n}) ((L_{C} - {\tilde{L}}_{C}) + ∣ {\tilde{L}}_{C} - E_{C} {\tilde{L}}_{C} ∣ + (1 - E_{C} {\tilde{L}}_{C})) .$ After expectation, the first and third terms together contribute $α_{n}$ to total variation (the factor $1 / 2$ in its definition is included).

2.1F1F3F4F6givenstep 1.1algebra

For fixed $C$ , expand $D (Q_{C} ∥ P_{Z}^{n})$ as an expectation over a uniform index $J$ and then $Z^{n} \sim W^{n} (\cdot ∣ U^{n} (J))$ . Averaging over codebooks and using symmetry lets us take $J = 1$ . The divergence and all rates use natural-log nats by [F6]. Conditional on $U^{n} (1), Z^{n}$ , the remaining codewords are independent and $E_{U^{n} (2), \dots, U^{n} (L_{n})} [\frac{Q_{C} (Z^{n})}{P_{Z}^{n} (Z^{n})}] = \frac{e^{S_{n}} + L_{n} - 1}{L_{n}} .$ For any finite positive random variable $A$ with law $p$ and mean $a$ , the vector $q_{i} = p_{i} A_{i} / a$ is a probability vector; [F4] gives $0 \leq D (p ∥ q) = \ln a - E [\ln A]$ . Thus $E \ln A \leq \ln E A$ . Applying this finite Jensen inequality to the displayed likelihood ratio gives $E_{C} D (Q_{C} ∥ P_{Z}^{n}) \leq E \ln (1 + e^{S_{n}} / L_{n}) .$

3.1F5F8step 2.1algebra

On $S_{n} \leq n (I + γ)$ , $L_{n} \geq e^{n R_{0}}$ and [F8] bound the logarithm by $e^{- n (R_{0} - I - γ)}$ . On the complement, $S_{n} \leq n B$ by the definition of $B$ , so $\ln (1 + e^{S_{n}} / L_{n}) \leq \ln 2 + n B$ . The complement has probability at most $ρ^{n}$ by [F5]. Splitting the expectation in step 2.1 across these two events proves the KL bound.

4.1F1F2F5step 1.2algebra∎

For fixed $z^{n}$ , let $A = {\tilde{L}}_{C} (z^{n}) - E_{C} {\tilde{L}}_{C} (z^{n})$ . The finite inequality $E ∣ A ∣ \leq \sqrt{E A^{2}}$ follows by expanding $0 \leq E (∣ A ∣ - E ∣ A ∣)^{2}$ . Independence of the $L_{n}$ codewords makes the cross terms vanish, so $E A^{2} = \frac{1}{L_{n}} (E_{U} [{\tilde{L}}_{1} (z^{n})^{2}] - (E_{U} {\tilde{L}}_{1} (z^{n}))^{2}) \leq \frac{E_{U} [{\tilde{L}}_{1} (z^{n})^{2}]}{L_{n}} .$ Since $0 \leq {\tilde{L}}_{1} \leq T$ and $E_{U} L_{1} (z^{n}) = \sum_{u^{n}} P_{U}^{n} (u^{n}) \frac{W^{n} (z^{n} ∣ u^{n})}{P_{Z}^{n} (z^{n})} = 1,$ the numerator is at most $T$ . Finite Cauchy–Schwarz with weights $P_{Z}^{n} (z^{n})$ then gives $\sum_{z^{n}} P_{Z}^{n} (z^{n}) E_{C} ∣ A ∣ \leq \sum_{z^{n}} P_{Z}^{n} (z^{n}) \sqrt{E_{C} A^{2}} \leq {(\sum_{z^{n}} P_{Z}^{n} (z^{n}))}^{1 / 2} {(\sum_{z^{n}} P_{Z}^{n} (z^{n}) E_{C} A^{2})}^{1 / 2} \leq \sqrt{T / L_{n}},$ where the middle inequality is finite Cauchy–Schwarz and $\sum_{z^{n}} P_{Z}^{n} (z^{n}) = 1$ . Together with step 1.2, this fluctuation contributes at most $\frac{1}{2} \sqrt{T / L_{n}}$ to expected total variation. Using [F5], $α_{n} \leq ρ^{n}$ , and $L_{n} \geq e^{n R_{0}}$ gives the stated bound.

LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck pendingOpen item page →

The finite wiretap auxiliary has cardinality at most |X|

Statement

For every finite joint law $P_{U X}$ on a finite wiretap channel with input alphabet $X$ , where $U - X - (Y, Z)$ means $P_{U X Y Z} (u, x, y, z) = P_{U X} (u, x) W (y, z ∣ x)$ , there is another finite auxiliary $\tilde{U}$ with $∣ \tilde{U} ∣ \leq ∣ X ∣$ whose value of $I (\tilde{U}; Y) - I (\tilde{U}; Z)$ is at least $I (U; Y) - I (U; Z)$ . Consequently

$\sup_{P_{U, X} : U - X - (Y, Z)} [I (U; Y) - I (U; Z)]$

is a maximum and may be restricted to $∣ U ∣ \leq ∣ X ∣$ . For each input law $q$ , the single-letter objective $q \mapsto I_{q} (X; Y) - I_{q} (X; Z)$ is continuous on the finite probability simplex.

Facts & Assumptions

Given: A finite wiretap channel, a finite auxiliary $U$ , and a joint law $P_{U X}$ with the stated Markov factorization.

[F1]

Finite discrete memoryless wiretap channel and code model: the input alphabet and both output alphabets are finite; conditional on $X$ , the marginals $Y$ and $Z$ use the finite DMCs $W_{Y}$ and $W_{Z}$ .

[F2]

Finite mutual information: mutual information is the finite joint-law KL sum in nats.

[F3]

Finite entropy and mutual-information chain rules: $I (A; B) = H (B) - H (B ∣ A)$ for finite variables.

[F4]

Finite distributions, entropy, divergence, and stochastic matrices: $H (p) = - \sum_{p_{i} > 0} p_{i} \ln p_{i}$ with $0 \ln 0 = 0$ .

[F5]

The natural logarithm is bounded above by its positive argument minus one: for $t \geq 1$ , $0 \leq \ln t \leq t - 1$ .

[F6]

Heine-Borel in $R^{n}$ : with the Euclidean metric a subset of $R^{n}$ is compact if and only if it is closed and bounded, and the proof by bisection uses no choice principle; the same holds on the real line: every closed bounded subset of finite-dimensional Euclidean space $R^{N}$ , $N \geq 1$ , is compact.

[F7]

A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value: a continuous real-valued function on a nonempty compact metric space attains its maximum.

Proof

1.1F1F2F3F4F5givencasesalgebra

If $m : = ∣ X ∣ = 1$ , then $X$ is constant and both mutual informations in the objective are zero, so $∣ \tilde{U} ∣ = 1$ suffices. Assume $m \geq 2$ . For a probability vector $q$ on $X$ , let $F (q) : = I_{q} (X; Y) - I_{q} (X; Z) .$ By [F2]–[F4] and the finite entropy identity in [F3], $F (q) = H (q W_{Y}) - H (q W_{Z}) - \sum_{x} q (x) (H (W_{Y} (\cdot ∣ x)) - H (W_{Z} (\cdot ∣ x))) .$ The maps $q \mapsto q W_{Y}$ and $q \mapsto q W_{Z}$ are finite linear maps. On $0 < t \leq 1$ , set $s = t^{- 1 / 2} \geq 1$ ; [F5] gives $0 \leq - t \ln t = 2 t \ln s \leq 2 \sqrt{t}$ . Hence $- t \ln t$ extends continuously to $t = 0$ with value $0$ , so finite entropy and $F$ are continuous on the simplex $Δ (X)$ .

2.1F1F2F3step 1.1algebra

Write $λ_{u} = P_{U} (u) > 0$ , $q_{u} = P_{X ∣ U = u}$ , and $\overset{ˉ}{q} = P_{X} = \sum_{u} λ_{u} q_{u}$ , omitting zero-mass $u$ . The chain rule [F3] gives $I (U; Y) - I (U; Z) = F (\overset{ˉ}{q}) - \sum_{u} λ_{u} F (q_{u}) .$ Indeed, expanding the right side by the entropy formula in step 1.1 leaves $H (Y) - \sum_{u} λ_{u} H (Y ∣ U = u) - H (Z) + \sum_{u} λ_{u} H (Z ∣ U = u)$ ; the linear conditional-on- $X$ terms cancel because $\overset{ˉ}{q} = \sum_{u} λ_{u} q_{u}$ , and the remaining expression is the left side.

3.1F1step 2.1chooseconstructalgebra

Suppose the current posterior mixture has $k > m$ positive weights. The $k$ vectors $(q_{u} (x_{1}), \dots, q_{u} (x_{m - 1}), 1)$ lie in $R^{m}$ , so there are coefficients $c_{u}$ , not all zero, with $\sum_{u} c_{u} = 0$ and $\sum_{u} c_{u} q_{u} (x_{j}) = 0$ for $j < m$ . Since each $q_{u}$ sums to one, the same relation holds for the last coordinate $x_{m}$ . The coefficients include both signs. Therefore the weights $λ_{u} + t c_{u}$ remain nonnegative on a bounded interval $[t_{-}, t_{+}]$ with $t_{-} < 0 < t_{+}$ ; at either endpoint at least one weight is zero, while the total weight and posterior average stay fixed. The average $G (t) = \sum_{u} (λ_{u} + t c_{u}) F (q_{u})$ is affine in $t$ , so at least one endpoint has $G (t) \leq G (0)$ : otherwise zero, a convex combination of $t_{-}$ and $t_{+}$ , would have a smaller value than both endpoints. Choose that endpoint and delete its zero weights. This keeps $\overset{ˉ}{q}$ fixed and does not decrease the wiretap objective in step 2.1.

4.1step 3.1induction

Repeating step 3.1 finitely many times reduces any finite auxiliary to at most $m$ positive weights, preserving $P_{X}$ and not decreasing $I (U; Y) - I (U; Z)$ . Thus every finite auxiliary is dominated by one with $∣ U ∣ \leq m$ .

5.1F6F7step 1.1step 4.1algebra∎

The parameter space $Δ_{m} \times Δ (X)^{m}$ of $m$ weights and $m$ posterior laws is a nonempty closed bounded subset of $R^{m + m^{2}}$ , since it is described by finitely many coordinate inequalities $0 \leq t \leq 1$ and coordinate-sum equalities. It is compact by [F6]. By step 1.1 the objective $F (\overset{ˉ}{q}) - \sum_{j = 1}^{m} λ_{j} F (q_{j})$ is continuous there, including zero weights, so it attains a maximum by [F7]. Step 4.1 shows this maximum equals the supremum over all finite auxiliaries.

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Strong-secrecy capacity of a finite DMC wiretap channel

Statement

Let $W (y, z ∣ x)$ be a finite wiretap DMC as in Finite discrete memoryless wiretap channel and code model, with no input-cost constraint, feedback, or preshared secret key. Let

$C (W) : = \max_{\begin{array}{c} U finite, P_{U, X} : U - X - (Y, Z) \end{array}} [I (U; Y) - I (U; Z)],$

where $U - X - (Y, Z)$ means the joint law factors as $P_{U} (u) P_{X ∣ U} (x ∣ u) W (y, z ∣ x)$ . The maximum is attained with $∣ U ∣ \leq ∣ X ∣$ . The four capacities defined in Operational weak and strong secrecy capacities are equal:

$C_{a v, w e a k} = C_{a v, s t r o n g} = C_{m a x, w e a k} = C_{m a x, s t r o n g} = C (W) .$

Facts & Assumptions

Given: A finite wiretap channel, the code model of Finite discrete memoryless wiretap channel and code model, and the four operational capacities of Operational weak and strong secrecy capacities.

[F1]

Finite discrete memoryless wiretap channel and code model: $W (y, z ∣ x)$ is row-stochastic on finite alphabets; its block law is $W^{n} (y^{n}, z^{n} ∣ x^{n}) = \prod_{i} W (y_{i}, z_{i} ∣ x_{i})$ ; encoders have no feedback or preshared key, messages are uniform, and Eve knows the code description.

[F2]

Operational weak and strong secrecy capacities: $R$ is achievable when ${lim inf}_{n} n^{- 1} \ln ∣ M_{n} ∣ \geq R$ , the selected error criterion tends to zero, and the selected weak or strong secrecy limit holds.

[F3]

Information leakage and equivocation for finite observations: leakage is $I (M; Z^{n})$ in nats and its normalized value is $n^{- 1} I (M; Z^{n})$ .

[F4]

Weak and strong secrecy for wiretap code sequences: weak secrecy is $n^{- 1} I (M; Z^{n}) \to 0$ ; strong secrecy is $I (M; Z^{n}) \to 0$ .

[F5]

Finite mutual information: $I (A; B) = D (P_{A B} ∥ P_{A} \otimes P_{B})$ for finite variables, and its finite sum is in nats.

[F6]

Finite entropy and mutual-information chain rules: for finite variables, mutual information obeys the chain rule and $I (A; B) = H (A) - H (A ∣ B)$ .

[F7]

Fano bound for erasure and out-of-alphabet estimates: if a uniform message $M$ is estimated from a finite observation $Y$ with error probability $p_{e}$ , then $(1 - p_{e}) \ln ∣ M ∣ \leq I (M; Y) + h_{2} (p_{e})$ .

[F8]

Information-density concentration for a fixed finite DMC input law: for a fixed finite DMC input law, its IID information-density sum has two-sided Chebyshev concentration about $n I$ and an exponential upper tail above $n (I + γ)$ for every $γ > 0$ .

[F9]

Finite DMC resolvability by random codebooks: for an induced finite DMC $U \to Z$ , a uniform codebook of $⌈ e^{n R_{0}} ⌉$ IID codewords has expected output divergence from $P_{Z}^{n}$ tending to zero whenever $R_{0} > I (U; Z)$ .

[F10]

The finite wiretap auxiliary has cardinality at most |X|: every finite $U - X - (Y, Z)$ is dominated in $I (U; Y) - I (U; Z)$ by an auxiliary of size at most $∣ X ∣$ , and the maximum is attained.

[F11]

The finite wiretap product law is stochastic: the finite wiretap block product is stochastic; the product formula preserves the coordinatewise memoryless factorization.

[F12]

Finite KL divergence is nonnegative with equality exactly at equal laws: finite relative entropy is nonnegative.

Proof

1.1F1F5F10givenalgebra

Let $C = C (W)$ . A constant $U$ gives value zero, so $C \geq 0$ . By [F10] the maximum is attained with finite $∣ U ∣ \leq ∣ X ∣$ , and [F5] makes each mutual information finite, so $C < \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 ∣ u) : = \sum_{x} P_{X ∣ U} (x ∣ u) W_{Y} (y ∣ x), Q_{Z} (z ∣ u) : = \sum_{x} P_{X ∣ U} (x ∣ u) W_{Z} (z ∣ x) .$ Each row sums to one because $P_{X ∣ 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)$ .

1.2F10givenchoose

Suppose $C > 0$ and fix any $0 \leq R < C$ . By [F10], choose a maximizing law $P_{U, X}$ . Choose $R^{'}$ with $R < R^{'} < C$ , then choose $R_{0} > I (U; Z)$ so that $R^{'} + R_{0} < I (U; Y)$ . Choose $γ_{Y} > 0$ with $R^{'} + R_{0} < I (U; Y) - γ_{Y}$ . For each $n$ , set $M_{n} = ⌈ e^{n R^{'}} ⌉$ , $L_{n} = ⌈ e^{n R_{0}} ⌉$ , and independently draw $M_{n} L_{n}$ words $U^{n} (m, l)$ from $P_{U}^{n}$ .

1.3F2F4F5F12givenalgebra

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 \leq I (M; Z^{n}) / n \leq I (M; Z^{n})$ for $n \geq 1$ ; maximal error tending to zero implies average error tending to zero.

1.4F3F7F12givenalgebra

For the converse, consider any sequence of wiretap codes with average error $p_{n} \to 0$ and weak leakage $ℓ_{n} : = I (M; Z^{n})$ satisfying $ℓ_{n} / n \to 0$ . Fano's bound [F7] gives $(1 - p_{n}) \ln ∣ M_{n} ∣ \leq I (M; Y^{n}) + h_{2} (p_{n}) = I (M; Y^{n}) - I (M; Z^{n}) + ℓ_{n} + h_{2} (p_{n}) .$ The binary entropy is bounded by $\ln 2$ , since [F12] applied to $(p_{n}, 1 - p_{n})$ and $(1 / 2, 1 / 2)$ gives $0 \leq \ln 2 - h_{2} (p_{n})$ .

1.5F1F6F11givenalgebra

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} ∣ V_{i}) - I (M; Z_{i} ∣ V_{i})] .$ Indeed, $A_{i} - A_{i - 1} = I (M; Y_{i} ∣ V_{i}) - I (M; Z_{i} ∣ V_{i})$ for each $i$ , and the sum telescopes.

2.1F1F5F8step 1.2givenalgebra

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} ∣ U^{n}} (x^{n} ∣ u^{n}) = \prod_{i = 1}^{n} P_{X ∣ U} (x_{i} ∣ 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 ∣ u) : = \sum_{x} P_{X ∣ U} (x ∣ u) W_{Y} (y ∣ x)$ and $Q_{Z} (z ∣ u) : = \sum_{x} P_{X ∣ U} (x ∣ u) W_{Z} (z ∣ 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 ∣ u)$ . For an output with $P_{Y}^{n} (y^{n}) > 0$ , assign score $- \infty$ if $Q_{Y}^{n} (y^{n} ∣ 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} ∣ U^{n} (m, l))}{P_{Y}^{n} (Y^{n})} > n (I (U; Y) - γ_{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 $σ_{Y}^{2} / (n γ_{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 $E_{U^{n}} [Q_{Y}^{n} (y^{n} ∣ U^{n}) / 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) - γ_{Y})}$ , so its indicator is bounded above by the ratio times $e^{- n (I (U; Y) - γ_{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^{'}, R_{0} \geq 0$ , $M_{n} L_{n} \leq 4 e^{n (R^{'} + R_{0})}$ , and $R^{'} + R_{0} < I (U; Y) - γ_{Y}$ . Thus the ensemble average message error tends to zero.

2.2F1F10F11step 1.5givenalgebra

The code and channel law factor as $P_{M} (m) P_{X^{n} ∣ M} (x^{n} ∣ m) \prod_{j = 1}^{n} W (y_{j}, z_{j} ∣ x_{j}) .$ In this finite sum, the time- $i$ factor $W (y_{i}, z_{i} ∣ x_{i})$ separates from all other coordinate factors. Therefore, after summing over the other inputs and outputs, $P (Y_{i} = y, Z_{i} = z ∣ M = m, X_{i} = x, V_{i} = v) = W (y, z ∣ 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} ∣ V_{i} = v} W$ is a finite auxiliary law allowed in the maximum defining $C$ . By [F10], $I (M; Y_{i} ∣ V_{i} = v) - I (M; Z_{i} ∣ V_{i} = v) \leq C .$ Average over positive-mass $v$ and sum over $i$ in step 1.5 to obtain $I (M; Y^{n}) - I (M; Z^{n}) \leq n C$ .

3.1F1F3F9step 2.1givenchoose

Use the same conditional product encoder law $P_{X^{n} ∣ U^{n}} (x^{n} ∣ u^{n}) = \prod_{i = 1}^{n} P_{X ∣ U} (x_{i} ∣ 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} ∣ u^{n}) = \prod_{i = 1}^{n} Q_{Z} (z_{i} ∣ u_{i})$ , where $Q_{Z} (z ∣ u) = \sum_{x} P_{X ∣ U} (x ∣ u) W_{Z} (z ∣ x)$ . Eve's conditional output law for message $m$ is the mixture of the $L_{n}$ induced $Q_{Z}^{n} (\cdot ∣ U^{n} (m, l))$ outputs. Let $d (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 $E_{C} d (C) \to 0$ . Let $a (C)$ be the codebook's average Bob error. Step 2.1 and finite averaging give $E_{C} a (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 (C_{n}) + d (C_{n})$ is no larger than its finite ensemble mean. Such a codebook exists by finite averaging, so this specifies a sequence with $a (C_{n}) + d (C_{n}) \to 0$ without countable choices.

4.1F1step 3.1givenconstructalgebra

Write $η_{n} = a (C_{n}) + d (C_{n})$ and, for each message $m$ , write $e_{m}$ for its Bob error and $d_{m} = D (P_{Z^{n} ∣ m, C_{n}} ∥ P_{Z}^{n})$ . Delete every message with $e_{m} > t_{n}$ or $d_{m} > t_{n}$ , where $t_{n} = \sqrt{η_{n}} + 1 / n$ . For each message, $1 {e_{m} > t_{n} or d_{m} > t_{n}} \leq (e_{m} + d_{m}) / t_{n}$ ; averaging over the uniform message bounds the deleted fraction by $η_{n} / t_{n} \leq \sqrt{η_{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} \leq 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.

5.1F3F5F12step 4.1givenalgebra

For the uniform message on the retained set $S_{n}$ , put ${\overset{ˉ}{P}}_{Z^{n}} = ∣ S_{n} ∣^{- 1} \sum_{m \in S_{n}} P_{Z^{n} ∣ m, C_{n}}$ . Expanding the finite KL sums and grouping terms gives the exact identity $\frac{1}{∣ S_{n} ∣} \sum_{m \in S_{n}} D (P_{Z^{n} ∣ m, C_{n}} ∥ P_{Z}^{n}) = \frac{1}{∣ S_{n} ∣} \sum_{m, z^{n} : P_{Z^{n} ∣ m, C_{n}} (z^{n}) > 0} P_{Z^{n} ∣ m, C_{n}} (z^{n}) \ln \frac{P_{Z^{n} ∣ m, C_{n}} (z^{n})}{P_{Z}^{n} (z^{n})} = \frac{1}{∣ S_{n} ∣} \sum_{m, z^{n} : P_{Z^{n} ∣ m, C_{n}} (z^{n}) > 0} P_{Z^{n} ∣ m, C_{n}} (z^{n}) \ln \frac{P_{Z^{n} ∣ m, C_{n}} (z^{n})}{{\overset{ˉ}{P}}_{Z^{n}} (z^{n})} + \sum_{z^{n} : {\overset{ˉ}{P}}_{Z^{n}} (z^{n}) > 0} {\overset{ˉ}{P}}_{Z^{n}} (z^{n}) \ln \frac{{\overset{ˉ}{P}}_{Z^{n}} (z^{n})}{P_{Z}^{n} (z^{n})} = I (M; Z^{n}) + D ({\overset{ˉ}{P}}_{Z^{n}} ∥ P_{Z}^{n}) .$ 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}) \leq ∣ S_{n} ∣^{- 1} \sum_{m \in S_{n}} d_{m} \leq t_{n} \to 0$ . Also $∣ S_{n} ∣ \geq (1 - \sqrt{η_{n}}) M_{n}$ and $M_{n} \geq e^{n R^{'}}$ , while $n^{- 1} \ln (1 - \sqrt{η_{n}}) \to 0$ ; hence ${lim inf}_{n} n^{- 1} \ln ∣ S_{n} ∣ \geq R^{'}$ . This constructs a maximal-error, strong-secrecy sequence at rate at least $R^{'}$ , and therefore every $R < C$ is achievable for all four criteria.

6.1F2F4step 1.2step 1.3step 1.4step 2.2givenalgebra∎

Substitute step 2.2 into step 1.4, divide by $n (1 - p_{n})$ , and use $p_{n} \to 0$ , $ℓ_{n} / n \to 0$ , and $0 \leq h_{2} (p_{n}) \leq \ln 2$ to get ${lim sup}_{n} n^{- 1} \ln ∣ M_{n} ∣ \leq 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)$ .

TheoremStatement: Literature-sourcedProof: AI-generatedprecheck pendingOpen item page →

Secrecy capacity of a finite degraded wiretap channel

Statement

If $W (y, z ∣ x)$ is a finite degraded wiretap channel in the sense of Finite degraded wiretap channel, then all four operational capacities in Operational weak and strong secrecy capacities are equal to

$\max_{P_{X}} [I (X; Y) - I (X; Z)],$

where $P_{X}$ ranges over probability vectors on the finite input alphabet and the output law is induced by $W$ . The maximum is attained.

Facts & Assumptions

Given: A finite wiretap channel with a stochastic degradation kernel $V (z ∣ y)$ satisfying $W (y, z ∣ x) = W_{Y} (y ∣ x) V (z ∣ y)$ .

[F1]

Finite degraded wiretap channel: for every input law $P_{X}$ , $P_{X Y Z} (x, y, z) = P_{X} (x) W_{Y} (y ∣ x) V (z ∣ y)$ ; this factorization is the finite Markov condition written $X - Y - Z$ .

[F2]

Finite mutual information: mutual information is finite joint-law KL in nats.

[F3]

Finite entropy and mutual-information chain rules: finite mutual information satisfies its chain rule.

[F4]

Data processing for a finite Markov chain, with equality condition: for finite $A - B - C$ , $I (A; C) \leq I (A; B)$ .

[F5]

The finite wiretap auxiliary has cardinality at most |X|: the auxiliary objective's maximum is attained, and $q \mapsto I_{q} (X; Y) - I_{q} (X; Z)$ is continuous on the finite input simplex.

[F6]

Strong-secrecy capacity of a finite DMC wiretap channel: each of the four operational weak/strong secrecy capacities equals the maximum over finite $U - X - (Y, Z)$ .

[F7]

Operational weak and strong secrecy capacities: the four operational capacities use the rate, reliability, and secrecy limits stated in its Definition.

Proof

1.1F1F4givenalgebra

Fix any finite $P_{U, X}$ and form the joint law $P_{U, X, Y, Z} (u, x, y, z) = P_{U, X} (u, x) W (y, z ∣ x)$ , which is the notation $U - X - (Y, Z)$ . For each $u$ with $P_{U} (u) > 0$ , the degraded factorization [F1] makes $X - Y - Z$ under the posterior law $P_{X ∣ U = u}$ , so [F4] gives $I (X; Z ∣ U = u) \leq I (X; Y ∣ U = u)$ . Averaging over $u$ yields $I (X; Z ∣ U) \leq I (X; Y ∣ U)$ .

1.2F2givenconstructalgebra

Conversely, for any input law $P_{X}$ , take $U = X$ . Then $U - X - (Y, Z)$ holds and $I (U; Y) - I (U; Z) = I (X; Y) - I (X; Z)$ . Thus the supremum over auxiliaries is at least the supremum of the displayed single-letter objective.

2.1F2F3step 1.1givenalgebra

The Markov condition $U - X - Y$ gives $I (U; Y ∣ X) = 0$ , so the chain rule [F3] yields $I (X; Y) = I (U; Y) + I (X; Y ∣ U)$ . Likewise $U - X - Z$ gives $I (X; Z) = I (U; Z) + I (X; Z ∣ U)$ . Subtracting these identities and using step 1.1 shows $I (U; Y) - I (U; Z) = I (X; Y) - I (X; Z) - (I (X; Y ∣ U) - I (X; Z ∣ U)) \leq I (X; Y) - I (X; Z) .$

3.1F5F6F7step 2.1step 1.2algebra∎

By [F5], choose an auxiliary law attaining the maximum in the general formula. Step 2.1 shows that replacing this law by $U = X$ at the same marginal $P_{X}$ cannot decrease its value, so this input law attains the maximum of the single-letter expression. Every input law is itself an allowed auxiliary with $U = X$ by step 1.2. Thus the auxiliary maximum equals the displayed maximum, and [F6] identifies it with all four capacities in the sense of [F7].

5 · Examples, counterexamples and false statements

None yet.

Secrecy and Information Privacy

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Classical leftover-hash bound with public side information

Statement

Facts & Assumptions

Proof

Finite-source privacy–utility region

Definition

Information leakage and equivocation for finite observations

Definition

The finite wiretap product law is stochastic

Statement

Facts & Assumptions

Proof

Finite discrete memoryless wiretap channel and code model

Definition

A finite kernel criterion for perfect privacy

Statement

Facts & Assumptions

Proof

Finite degraded wiretap channel

Definition

Weak and strong secrecy for wiretap code sequences

Definition

Information-density concentration for a fixed finite DMC input law

Statement

Facts & Assumptions

Proof

Operational weak and strong secrecy capacities

Definition

Finite DMC resolvability by random codebooks

Statement

Facts & Assumptions

Proof

The finite wiretap auxiliary has cardinality at most |X|

Statement

Facts & Assumptions

Proof

Strong-secrecy capacity of a finite DMC wiretap channel

Statement

Facts & Assumptions

Proof

Secrecy capacity of a finite degraded wiretap channel

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources