Polynomial almost strongly universal hashing ($h_{a,b}(m)=b+{\sum }_{j=1}^L{m}_j{a}^j$)

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.