= Strongly universal hash family
{title2=$\Pr_h[h(x)=u,h(y)=v]=q^{-2}$}
= Strongly universal2 hashing
{synonym}
A <strongly universal hash family> makes every <ordered pair> of <outputs> equally likely: for distinct <inputs> $x,y$ and arbitrary specified <outputs> $u,v$,
$$
\Pr_h[h(x)=u,h(y)=v]=\frac1{q^2}.
$$
Thus the two <outputs> are <independent random variables>, each with the <uniform distribution on a finite set>. Adding the $q$ equal <ordered pairs> gives collision <probability> $q/q^2=1/q$, so the family is also a <universal hash family>.
Here is a completely enumerable example. In the <finite field> $\mathbb F_5$, take the <affine functions> $h_{a,b}(x)=ax+b$, using <modular arithmetic> modulo $5$. Choose $a$ and $b$ as <independent random variables>, each with the <uniform distribution on a finite set> of all five <finite field> elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely <hash functions>. For $x=0,y=1$, the <ordered pair> is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.
\Image[/affine-hash-pair-grid.png]
{title=Enumerating all affine hash functions over the finite field with five elements}
{description=Each cell shows the unique coefficient pair (a,b) producing the displayed outputs at 0 and 1. Removing a = 0 deletes the diagonal and leaves dependent outputs despite uniform individual values.}
Each row contains five choices, so each individual <output> has <probability> $5/25=1/5$. Each cell has <probability> $1/25$, and the five diagonal cells give collision <probability> $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: a nonzero <finite field> element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.
The example uses equal-sized <input> and <output> <sets> to make every choice visible; it illustrates the family definitions rather than compression. In a larger <input> <set>, a <hash function> cannot avoid all collisions into five buckets. What a <universal hash family> controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.
Restricting to $a\ne0$ leaves $20$ <permutations> with zero collision <probability> for distinct <inputs>. Individual <outputs> remain uniform, but given $h(0)=u$, the four values other than $u$ each have <conditional probability> $1/4$ and $u$ has zero. Hence these <outputs> are not <independent random variables>: this is a <universal hash family> but not a <strongly universal hash family>. Finally, the full $25$-member example contains five constant <functions>, with immediately visible collisions. Its pair guarantee concerns a random choice of <hash function>, and makes no claim of cryptographic <collision resistance>.
Back to article page
