Pairwise independent hash families

Let $U$ be a finite set, let $R$ be a nonempty finite set, and let $\mathcal{H}$ be a nonempty finite family of functions $h:U\to R$. The family $\mathcal{H}$ is pairwise independent when for every two distinct inputs $x,x^{\mathrm{\prime }}\in U$ and every two outputs $y,y^{\mathrm{\prime }}\in R$,

${\mathbb{P}}_{h\in \mathcal{H}}(h(x)=y\text{ and }h(x^{\mathrm{\prime }})=y^{\mathrm{\prime }})=\frac{1}{\mathrm{\mid }R{\mathrm{\mid }}^2},$

where $h$ is chosen uniformly from $\mathcal{H}$.

• If $U$ has at least two elements, pairwise independence forces each individual value $h(x)$ to be uniform on $R$ by summing over the second output coordinate.
• The definition does not require joint independence on triples or larger subfamilies of inputs.
• When $\mathrm{\mid }U\mathrm{\mid }<2$, the pairwise condition is vacuous; only the nonempty source and target-family hypotheses remain substantive.