Universal hash function

A universal hash function is a family of functions such that, for every pair of distinct inputs, a uniformly sampled maps them to the same output with probability at most . The variants below bound other statistics of the pair . All probabilities are over alone; no computational assumption is involved.

Universal

is universal if for all distinct ,

— CW79, who call such a family universal.

Strongly universal

is strongly universal (pairwise independent) if for all distinct and all ,

— WC81. More generally, is strongly universal (-wise independent) if is uniform on for all distinct — WC81.

Summing over shows that a strongly universal family is universal; when , summing over shows that is uniform on for each — standard.

Almost universal

For , is -almost universal (-AU) if for all distinct ,

— standard. A universal family is -AU.

Almost XOR-universal

For , is -almost XOR-universal (-AXU) if for all distinct and all ,

— Kra94, Rog95. Over an abelian group with in place of , the notion is -almost -universal — standard. The case shows that an -AXU family is -AU; summing over shows when ; a strongly universal family into is -AXU, since is uniform — standard.

Examples

Modular affine maps. For a prime , and with , the family with and is universal — CW79.

Affine maps over a field. For a finite field , the family with is strongly universal : for , the map is a bijection . Polynomials of degree less than with uniform coefficients are -wise independent in the same way — standard.

Polynomial evaluation. For a finite field and a fixed length , the family of functions ,

is -almost -universal: for and , is a nonzero polynomial in of degree at most , since its coefficient of is for some , and so it has at most roots (see Schwartz–Zippel lemma). Over it is -AXU, and in particular -AU — standard. The same formula on messages of varying length is not almost universal, since appending a zero block leaves unchanged; such messages are first encoded injectively into — standard.

Uses

Wegman–Carter one-time MACs are built from these families — WC81; so are nonce-based Wegman–Carter MACs — standard. The LRW2 tweakable block cipher uses an almost XOR-universal family — LRW02. The leftover hash lemma extracts nearly uniform bits with a universal family — ILL89, HILL99.

Participates in

Used via Universal hash function