TheoremStatement: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pending

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.

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.

Used by

Nothing in the library uses this result yet.

Dependency tree · 0 levels

Nothing. This result depends on no other item in the library.

Sources

Prakash Narayan and Himanshu Tyagi, Multiterminal Secrecy by Public Discussion, Foundations and Trends in Communications and Information Theory 13(2–3), 2016 (standard reference, not scraped)
C. H. Bennett, G. Brassard, C. Crépeau, and U. Maurer, Generalized Privacy Amplification, IEEE Transactions on Information Theory 41(6), 1995 (standard reference, not scraped)