Engineering / Mathematics — Discrete Probability
Pairwise Independence and Universal Hash Families
Constructing pairwise independent hash families over finite fields and why the weaker independence suffices.
Executive summary
A pairwise independent family makes any two outputs jointly uniform, which is far stronger than universality and still achievable with a constant number of random field elements.
The standard construction is an affine map over a finite field, and its analysis is a two-line argument in linear algebra.
Learning objectives
- Construct a pairwise independent family over a finite field.
- Prove the pairwise independence property.
- Identify the analyses that require only this level.
01The affine construction
Affine family over a field
Over a finite field F, define h_{a,b}(x) = ax + b for a, b ∈ F chosen uniformly.
Pairwise independence
For distinct x ≠ y and any targets s, t, exactly one pair (a, b) satisfies h(x) = s and h(y) = t.
Reason. The two equations form a linear system in (a,b) with matrix determinant x − y ≠ 0, hence a unique solution.
So the pair (h(x), h(y)) is uniform over F × F, which is exactly pairwise independence. Only two field elements of randomness are consumed, independent of the domain size.
02Extending to k-wise independence
Replacing the affine map with a polynomial of degree k − 1 gives k-wise independence, by the same argument via the invertibility of the Vandermonde matrix on distinct points.
h_{a₀,...,a_{k−1}}(x) = a₀ + a₁x + ... + a_{k−1}x^{k−1}- Pairwise
2 field elementsSecond-moment arguments, collision bounds - k-wise
k field elementsHigher-moment concentration - Fully random
|D| log|R| bitsExponential tail bounds; usually unaffordable
03Where it suffices
Any argument resting on expectation or variance needs only pairwise independence, because variance of a sum decomposes under pairwise independence alone.
Hash table chain length
Expected chain length bounds follow from universality; variance bounds from pairwise independence.
Collision counting
The expected number of colliding pairs is a sum of indicator expectations, needing only pairwise behaviour.
Leftover hash lemma
Extracts near-uniform bits from a high-entropy source using only a universal family.
Second-moment sampling
Chebyshev-based estimation of a proportion, with variance from pairwise independence.
What it does not suffice for is amplification by repeated independent trials, where failure probabilities must multiply. That needs mutual independence across the trials, which is supplied by fresh randomness per trial rather than by a hash family.
04Frequently asked questions
Is pairwise independence strictly stronger than universality?
Yes. Pairwise independence implies the universal collision bound, but a universal family need not have uniform individual outputs. Universality constrains collisions only.
Why use a field rather than integers modulo a composite?
Because the construction needs x − y to be invertible for distinct x and y, which requires no zero divisors. Over a composite modulus the argument fails for differences sharing a factor with the modulus.
How much randomness does k-wise independence cost?
k field elements, so roughly k log|D| bits. This grows with k but remains far below the domain size, which is what makes bounded independence useful.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 125-127.
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.