= Almost strongly universal hash family
{title2=$\Pr_h[h(x)=u,h(y)=v]\leq\varepsilon/q$}
= Almost strongly universal2 hashing
{synonym}
An <almost strongly universal hash family> relaxes the exact <ordered pair> balance of a <strongly universal hash family>. In the convention used here, choose $h$ with the <uniform distribution on a finite set> from a family with $q$ possible <outputs>. Every individual <output> remains uniform, and for every distinct pair of <inputs> $x,y$ and every specified <ordered pair> of <outputs> $u,v$,
$$
\Pr_h[h(x)=u,h(y)=v]\leq\frac{\varepsilon}{q}.
$$
Equivalently, the <conditional probability> $\Pr_h[h(y)=v\mid h(x)=u]$ is at most $\varepsilon$. This asks how predictable a second <output> can become after the first is known.
For $q=5$, <strongly universal hash families> give $\varepsilon=1/5$: learning one <output> leaves each specified second <output> with <conditional probability> $1/5$. A looser guarantee $\varepsilon=2/5$ permits a specified <ordered pair> to have <probability> as large as $2/25$, while each individual <output> still has <probability> $1/5$. Summing over the five equal <ordered pairs> bounds the collision <probability> by $2/5$, rather than the $1/5$ required of a <universal hash family>. Thus an <almost strongly universal hash family> need not be a <universal hash family>. Necessarily $\varepsilon\geq1/q$, because the $q$ conditional <probabilities> sum to one; equality recovers a <strongly universal hash family>. This relaxation is useful in <Wegman–Carter authentication>, where efficiency can be traded against a quantified forgery bound within a complete <message authentication> protocol.
Back to article page
