Almost strongly universal hash family (${\mathrm{Pr}}_h[h(x)=u,h(y)=v]\le \epsilon /q$)

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$,Equivalently, the conditional probability ${\mathrm{Pr}}_h[h(y)=v\mid h(x)=u]$ is at most $\epsilon$. This asks how predictable a second output can become after the first is known.

For $q=5$, strongly universal hash families give $\epsilon =1/5$: learning one output leaves each specified second output with conditional probability $1/5$. A looser guarantee $\epsilon =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 $\epsilon \ge 1/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.

For fixed-length messages in ${\mathbb{F}}_q^L$, choose independent uniform field elements $a,b$. Each output is uniform because $b$ masks it. For distinct messages and prescribed output difference $d$, the equation ${\sum }_{j=1}^L(m_j^{\prime }-m_j)a^j=d$ is a nonzero polynomial equation of degree at most $L$, so the root bound for a polynomial gives at most $L$ choices of $a$. The joint output probability is at most $L/q^2$. Thus the family is $(L/q)$-almost strongly universal when $L<q$. Starting the message polynomial at power one matters: using a freely varying message coefficient at power zero would permit a known constant tag shift after observing one tag.