Randomness can be economical: a short seed can give every pair of hash values the right joint distribution even when the entire collection is not mutually independent. This distinction matters when applying variance bounds or reasoning about collisions. We use a prime field so every nonzero element has a multiplicative inverse.
Two random coefficients
Definition 1.4.1
(Affine hash family over a prime field)
Fix a prime and write . A seed is a pair chosen independently and uniformly from , and the hash function it selects is
The family has equally likely members, and the case is included.
The inputs considered below are fixed before the random seed is chosen. For one fixed and any , there are exactly choices of with (one for each ), so is uniform. The stronger statement concerns two keys at once.
Theorem 1.4.2
(Pairwise independence of affine hashing)
Let be fixed elements of . For every ,
Consequently and are independent and each is uniform on .
Proof
(Solving a two-by-two linear system for the seed)
The equations and imply . Since in the field, has an inverse, so is forced, and then is forced. Conversely this pair satisfies both equations. Hence exactly one of the equally likely seeds produces the value pair , which gives probability . Summing over shows each value has probability , and the joint probability is the product .
Proof X-ray
Solve for the seed
The one non-routine move is to read the question "which seeds give these two values?" as a linear system in the unknowns , not in . The only hypothesis that does work is in the field: it makes the coefficient invertible, which is exactly why is prime and why the keys must be distinct field elements. The case must remain in the seed distribution. It is the seed that sends both keys to , and excluding it changes the joint distribution, as the common mistakes below show. The argument counts seeds and never uses the specific values of , so it holds for all value pairs at once.
Summing the cases yields . This statement assumes distinct field elements: two integers with the same residue are not distinct inputs to this hash. It also assumes the inputs are fixed independently of the seed; an adversary who first sees the seed is a different model.
Three keys and a misleading inference
Let and fix keys . If , the three values are . If , they are . More generally, if multiplication by is injective, so none of the three distinct keys collide; if , all three collide. Since is uniform,
The expectation also follows by linearity from the three pairwise collision probabilities. The union bound gives ; it is valid but loose here. For fixed distinct field elements, the same union-bound reasoning gives at most (and of course any probability is at most one). For this particular affine family, when , the exact probability of at least one collision is : in fact either all keys collide or none do. This conclusion should not be assumed for an arbitrary pairwise-independent family.
Counterexample mode
Pairwise independent values, dependent collision events
For the three fixed keys, each pair of hash values is independent. Yet the events and are both exactly the event . Their joint probability is , not . Multiplying their probabilities would be invalid. Also in , so the three hash values are not mutually independent.
Worked examples
Worked example 1.4.3
(Finding the seed for prescribed values)
Let , keys , , and target values , . Then and, modulo , , , and because . Hence and . Check: and . Both targets are met, and the computation shows no other seed does.
Worked example 1.4.4
(Collision count for three keys over )
Take keys in . The seed gives values , with no collision. The seed gives , three colliding pairs. Only (seven seeds out of ) produces a collision, so , matching three pairs times each.
Worked example 1.4.5
(Keys that agree modulo q)
Let and use the integers and as keys. Since , they are the same field element, and for every seed, a collision probability of rather than . The theorem does not apply because fails in . Replacing by the distinct residue restores the collision probability .
Common mistake
(Dropping to avoid a trivial hash)
The function is constant, so it can look like a degenerate case to discard. If is restricted to nonzero values, the pair can never be equal for , so , and the joint law of the two values is no longer uniform on . Pairwise independence needs the full seed space.
Common mistake
(Treating integers as field elements)
The theorem is about distinct elements of . Keys that differ by a multiple of collide with probability . Reduce keys modulo first, or use a prime larger than the largest key.
What the seed buys
There are equally likely functions indexed by the two field elements; storing the seed requires two field elements. With fixed , a straightforward evaluation uses one field multiplication and one addition per key. Exact bit costs depend on the representation and arithmetic implementation. Pairwise independence suffices for some variance calculations, but it does not justify a product of arbitrary event probabilities or the full-independence hypotheses of an exponential-tail argument. If keys are arbitrary long strings, an additional encoding or hash construction and its own collision analysis are required.
Exercises
Quick check
(With , , , compute .)
Reduce modulo .
Solution · Answer
.
Quick check
(For distinct fixed , what is ?)
Sum over .
Solution · Answer
Each of the values of contributes , so the total is .
Quick check
(For three distinct fixed field keys, compute the expected number of colliding pairs.)
Use linearity over the three pairs.
Solution · Answer
There are three pairs, each colliding with probability , so the expectation is . Linearity needs no independence between the collision events, which are in fact dependent.
Quick check
(If and are integers differing by , can the distinct-field-elements claim be applied?)
Compare their residues.
Solution · Answer
No. Their residues coincide, so they are one field element and always hash identically under this map: the collision probability is , not .