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.

✓ 3 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 3 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Secrecy and Information Privacy — Examples

1 · Prerequisites

2 · Summary

These examples separate normalized from unnormalized leakage, compute a finite binary privacy–utility objective and its perfect-privacy boundary, and evaluate a degraded binary erasure wiretap channel. Each calculation uses finite alphabets and natural-log nats.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck pendingOpen item page →

A finite information-bottleneck privacy model

Statement

Let $S$ be a fair bit, let $N \sim Bernoulli (1 / 10)$ be independent, and set $Y = S \oplus N$ . For every finite stochastic release kernel $K (z ∣ y)$ , the induced law is $S - Y - Z$ . With $h (p) : = - p \ln p - (1 - p) \ln (1 - p)$ and $0 \ln 0 : = 0$ ,

$I (Y; Z) - \frac{1}{2} I (S; Z) \leq \frac{1}{2} \ln 2 + \frac{1}{2} h (1 / 10),$

and equality is attained by releasing $Z = Y$ (or any bijective relabeling of $Y$ ). If $I (S; Z) = 0$ , then necessarily $I (Y; Z) = 0$ for every such release kernel.

Facts & Assumptions

Given: A fair sensitive bit $S$ , independent noise $N \sim Bernoulli (1 / 10)$ , useful bit $Y = S \oplus N$ , and a finite release kernel $K (z ∣ y)$ .

[F1]

Finite-source privacy–utility region: the kernel induces $P_{S Y Z} = P_{S Y} K_{Z ∣ Y}$ , written $S - Y - Z$ , with leakage $I (S; Z)$ and retained-information utility $I (Y; Z)$ .

[F2]

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

[F3]

Finite conditional entropy: conditional entropy is the finite average of the conditional entropies, with zero-mass branches omitted.

[F4]

Finite entropy and mutual-information chain rules: mutual information equals the corresponding entropy difference and the finite entropy chain rule holds.

[F5]

A finite kernel criterion for perfect privacy: $I (S; Z) = 0$ exactly when each positive-support conditional output law $P_{Z ∣ S = s}$ is the same across $s$ .

[F6]

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

Proof

1.1F1F3F6givenalgebra

The fair bit $S$ has entropy $\ln 2$ . Since $S$ is fair and independent of the symmetric noise, $Y$ is fair as well. Given either value of $Y$ , the posterior error probability for estimating $S$ is $1 / 10$ , so $H (S ∣ Y) = h (1 / 10)$ . The factorization in [F1] is $P_{S Y Z} = P_{S Y} K_{Z ∣ Y}$ .

2.1F1F2F3F4F6step 1.1algebra

Using [F2] and [F4], expand the objective as $I (Y; Z) - \frac{1}{2} I (S; Z) = \frac{1}{2} \ln 2 - H (Y ∣ Z) + \frac{1}{2} H (S ∣ Z) .$ The conditional-entropy chain rules in [F4] give $H (S, Y ∣ Z) = H (S ∣ Z) + H (Y ∣ S, Z) = H (Y ∣ Z) + H (S ∣ Y, Z)$ . By [F3] and [F6], $H (Y ∣ S, Z) \geq 0$ and $H (Y ∣ Z) \geq 0$ , so $H (S ∣ Z) \leq H (S, Y ∣ Z)$ . The factorization in [F1] gives $P_{S ∣ Y, Z} = P_{S ∣ Y}$ on positive-mass pairs, hence $H (S ∣ Y, Z) = H (S ∣ Y) = h (1 / 10)$ by step 1.1. Therefore $H (S ∣ Z) \leq H (Y ∣ Z) + h (1 / 10)$ , and $I (Y; Z) - \frac{1}{2} I (S; Z) \leq \frac{1}{2} \ln 2 + \frac{1}{2} h (1 / 10) - \frac{1}{2} H (Y ∣ Z) \leq \frac{1}{2} \ln 2 + \frac{1}{2} h (1 / 10)$ .

2.2F2F3F4step 1.1algebra

For the identity release $Z = Y$ , $H (Y ∣ Z) = 0$ and step 1.1 gives $I (S; Y) = H (S) - H (S ∣ Y) = \ln 2 - h (1 / 10)$ . Substitution gives equality in the bound. A bijective relabeling preserves these conditional entropies and mutual informations, so also attains equality.

3.1F1F5step 1.1algebra∎

Suppose $I (S; Z) = 0$ . By [F5], for each $z$ with $P_{Z} (z) > 0$ , the two rows of $P_{Z ∣ S}$ agree. If $P_{Z} (z) = 0$ , then $0 = \frac{1}{2} P (z ∣ S = 0) + \frac{1}{2} P (z ∣ S = 1)$ , and nonnegativity forces both entries to be zero, so the rows agree for every release value. With row order $s = 0, 1$ and $y = 0, 1$ , the binary symmetric channel matrix from $S$ to $Y$ is $T = (\begin{array}{cc} 9 / 10 & 1 / 10 \\ 1 / 10 & 9 / 10 \end{array}),$ so for the column $k_{z} = (K (z ∣ 0), K (z ∣ 1))^{T}$ the output column is $T k_{z} = c_{z} (1, 1)^{T}$ for some $c_{z}$ . Since $\det T = 4 / 5 \neq 0$ and $T (1, 1)^{T} = (1, 1)^{T}$ , invertibility gives $k_{z} = c_{z} (1, 1)^{T}$ . This holds for every $z$ , so the two rows of $K$ coincide and $Y, Z$ are independent. Therefore $I (Y; Z) = 0$ .

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck pendingOpen item page →

Weak secrecy does not imply strong secrecy

Statement

Consider the noiseless finite wiretap channel with $X = Y = Z = {0, 1}$ and $W (y, z ∣ x) = 1$ exactly when $y = z = x$ . At blocklength $n$ , let $k_{n} = ⌊ \sqrt{n} ⌋$ , let $M_{n}$ be uniform on ${0, 1}^{k_{n}}$ , and transmit $X^{n} = (M_{n}, 0^{n - k_{n}})$ . Bob and Eve both observe the transmitted word exactly. This reliable code sequence satisfies weak secrecy but not strong secrecy: its leakage is $I (M_{n}; Z^{n}) = k_{n} \ln 2 \to \infty$ , whereas $n^{- 1} I (M_{n}; Z^{n}) \to 0$ . In general, strong secrecy implies weak secrecy.

Facts & Assumptions

Given: The finite wiretap code model, finite mutual information and the weak/strong secrecy criteria.

[F1]

Finite discrete memoryless wiretap channel and code model: a wiretap code has a uniform message, Bob observes $Y^{n}$ , Eve observes $Z^{n}$ , and error includes erasure.

[F2]

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

[F3]

Weak and strong secrecy for wiretap code sequences: weak secrecy requires normalized leakage to vanish, while strong secrecy requires unnormalized leakage to vanish.

[F4]

Finite mutual information: $I (M; Z^{n}) = D (P_{M Z^{n}} ∥ P_{M} \otimes P_{Z^{n}})$ for finite variables.

[F5]

Finite entropy and mutual-information chain rules: $I (M; Z^{n}) = H (M) - H (M ∣ Z^{n})$ and the entropy chain rule holds for finite variables.

[F6]

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

[F7]

Finite distributions, entropy, divergence, and stochastic matrices: a uniform law on $N$ points has entropy $\ln N$ .

Proof

1.1F1givenconstruct

For each $n$ , the input string has length $k_{n} + (n - k_{n}) = n$ . The noiseless channel gives $Y^{n} = Z^{n} = X^{n}$ with probability one, so Bob recovers the first $k_{n}$ bits exactly and the error probability is zero. Eve's observation also determines $M_{n}$ exactly, hence $H (M_{n} ∣ Z^{n}) = 0$ .

2.1F5F7step 1.1algebra

By uniformity and [F7], $H (M_{n}) = \ln (2^{k_{n}}) = k_{n} \ln 2$ . Thus [F5] gives $I (M_{n}; Z^{n}) = H (M_{n}) - H (M_{n} ∣ Z^{n}) = k_{n} \ln 2$ .

3.1F2F3step 2.1algebra

Since $\sqrt{n} - 1 < k_{n} \leq \sqrt{n}$ , one has $k_{n} \to \infty$ and $k_{n} / n \to 0$ . Step 2.1 therefore gives unnormalized leakage tending to infinity and normalized leakage tending to zero by [F2]. With zero error this is weak secrecy and failure of strong secrecy by [F3].

4.1F2F3F4F6algebra∎

For any wiretap code sequence, [F4] identifies mutual information with finite KL divergence, and [F6] makes it nonnegative. Hence $0 \leq I (M_{n}; Z^{n}) / n \leq I (M_{n}; Z^{n})$ for $n \geq 1$ . If the right side tends to zero, so does the left side, proving that strong secrecy implies weak secrecy.

ExampleConstruction: Literature-sourcedVerification: AI-generatedprecheck pendingOpen item page →

A degraded binary erasure wiretap channel

Statement

Bob observes a binary erasure channel (BEC) with input alphabet ${0, 1}$ , output alphabet ${0, 1, e}$ , and erasure probability $1 / 4$ . Eve observes Bob's output after independently erasing each surviving bit with probability $1 / 3$ , while an erasure remains an erasure. This is a finite degraded wiretap channel. Its strong- and weak-secrecy capacities under average or maximal error are all $\ln 2 / 4$ nats per use. Define $h (p) : = - p \ln p - (1 - p) \ln (1 - p)$ with $0 \ln 0 : = 0$ . For Bernoulli- $p$ input the single-letter difference is $h (p) / 4$ , which is zero at $p = 0, 1$ and maximal at $p = 1 / 2$ .

Facts & Assumptions

Given: Bob's channel is BEC $(1 / 4)$ and Eve's output is obtained by an independent BEC $(1 / 3)$ erasure of Bob's non-erased symbols.

[F1]

Finite degraded wiretap channel: a degraded wiretap channel has factorization $W (y, z ∣ x) = W_{Y} (y ∣ x) V (z ∣ y)$ .

[F2]

Secrecy capacity of a finite degraded wiretap channel: all four operational secrecy capacities equal $\max_{P_{X}} [I (X; Y) - I (X; Z)]$ .

[F3]

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

[F4]

Finite entropy and mutual-information chain rules: finite mutual information satisfies $I (X; Y) = H (X) - H (X ∣ Y)$ and the entropy chain rule.

[F5]

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

[F6]

Finite distributions, entropy, divergence, and stochastic matrices: $h (p) = - p \ln p - (1 - p) \ln (1 - p)$ with zero terms omitted, and the uniform binary entropy is $\ln 2$ .

Proof

1.1F1givenconstructalgebra

Define $V (e ∣ e) = 1$ , $V (y ∣ y) = 2 / 3$ , and $V (e ∣ y) = 1 / 3$ for $y \in {0, 1}$ , with all other entries zero. Each row sums to one. Given input $x$ , the joint probabilities are $W_{Y} (e ∣ x) V (e ∣ e) = 1 / 4$ for $(Y, Z) = (e, e)$ , $W_{Y} (x ∣ x) V (x ∣ x) = (3 / 4) (2 / 3) = 1 / 2$ for $(x, x)$ , and $W_{Y} (x ∣ x) V (e ∣ x) = (3 / 4) (1 / 3) = 1 / 4$ for $(x, e)$ ; all other pairs have probability zero. Thus $W (y, z ∣ x) = W_{Y} (y ∣ x) V (z ∣ y)$ and [F1] applies.

2.1F3F4F6step 1.1algebra

For a Bernoulli- $p$ input, a BEC with erasure probability $ϵ$ has $H (X ∣ Y) = ϵ h (p)$ : on a received bit the conditional entropy is zero, and on erasure it is $H (X) = h (p)$ . Since $I (X; Y) = H (X) - H (X ∣ Y)$ by [F4], Bob's mutual information is $(3 / 4) h (p)$ and Eve's is $(1 / 2) h (p)$ . Their difference is $h (p) / 4$ .

3.1F2F5F6step 2.1algebra∎

For every $p \in [0, 1]$ , compare the Bernoulli- $p$ law with the uniform binary law. By [F5], $0 \leq D ((p, 1 - p) ∥ (1 / 2, 1 / 2)) = \ln 2 - h (p),$ with equality exactly when $p = 1 / 2$ . At $p = 0$ and $p = 1$ , the zero-term convention in [F6] gives $h (p) = 0$ . Thus $h (p) / 4$ has maximum $\ln 2 / 4$ at the fair input and vanishes at both deterministic endpoints. The capacity claim follows from [F2] and step 2.1.

Secrecy and Information Privacy — Examples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A finite information-bottleneck privacy model

Statement

Facts & Assumptions

Proof

Weak secrecy does not imply strong secrecy

Statement

Facts & Assumptions

Proof

A degraded binary erasure wiretap channel

Statement

Facts & Assumptions

Proof

Sources