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