Engineering / Mathematics — Discrete Probability
Measures of Randomness and the Leftover Hash Lemma
Min-entropy, randomness extraction, and the leftover hash lemma that converts weak randomness into near-uniform bits.
Executive summary
Physical randomness sources are biased and correlated. Min-entropy measures the usable randomness in such a source, and the leftover hash lemma shows that a universal hash family extracts near-uniform bits from it.
The lemma is the theoretical foundation of practical randomness conditioning.
Learning objectives
- Define min-entropy and contrast it with Shannon entropy.
- State the leftover hash lemma.
- Apply the entropy loss parameter to size an extractor.
01Min-entropy
Min-entropy
For a distribution X, H∞(X) = −log₂ max_s P(X = s).
Min-entropy is governed entirely by the most likely outcome, which is the right pessimism for cryptography: a source is only as unpredictable as its best single guess.
| Source | Shannon entropy | Min-entropy |
|---|---|---|
| Uniform on 2^n values | n | n |
| Fixed value w.p. 1/2, else uniform on 2^n | ≈ n/2 + 1 | 1 |
| Biased bit, p = 0.9 | 0.469 | 0.152 |
02The leftover hash lemma
Leftover hash lemma
Let X have min-entropy at least m, and let H be a universal family mapping into {0,1}^ℓ with ℓ = m − 2log(1/ε). For a uniformly chosen key k,
Δ((k, h_k(X)), (k, U)) ≤ ε,
where U is uniform on {0,1}^ℓ.
Two features matter. The key is included in the output distribution, so the extracted bits remain near-uniform even to someone who knows which hash function was used — the key need not be secret. And only universality is required, so the extractor is cheap.
Entropy loss = 2 log₂(1/ε) bits — for ε = 2^{−64}, that is 128 bits03Practical extraction
Estimate min-entropy
Assess the source conservatively; underestimating is safe, overestimating is not.
Choose the security parameter
Fix ε, typically 2^{−64} or smaller, giving a 128-bit entropy loss.
Size the output
Extract at most m − 2log(1/ε) bits.
Apply the extractor
Hash the source output with a universal family under a public key.
The entropy loss is the price of near-uniformity and it is unavoidable: extracting the full min-entropy would give bits distinguishable from uniform. Operating systems condition raw entropy this way before seeding a deterministic generator.
04Frequently asked questions
Why is the key included in the output distribution?
Because otherwise the lemma would be false — a specific key can correlate with the source. Including it asserts the stronger and more useful property that the output looks uniform even given full knowledge of the extractor used.
Can more bits be extracted with a stronger family?
The 2log(1/ε) loss is essentially optimal for this style of extractor. Reducing it requires either a weaker closeness requirement or extractors using additional structure in the source.
What if the min-entropy is overestimated?
The output is not close to uniform and the guarantee is void, silently. This is why entropy estimation for hardware sources is conservative and why health tests run continuously rather than at initialisation only.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 136-141.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.