the family ${\mathcal{H}}$ is *${\varepsilon}$-Almost Strongly Universal$_2$ (${\varepsilon}$-ASU$_2$)*.

When proving security of an authentication scheme, there are two probabilities to bound: the probability of success in an *impersonation* attack, and the probability of success in a *substitution* attack. In an impersonation attack, the adversary pretends to be a legitimate user and tries to generate the correct tag for a (forged) message with no additional information, as would be given by a valid message-tag pair. In a substitution attack, the adversary intercepts a valid message-tag pair and tries to replace it with a new message-tag pair. This latter attack is more powerful than the former [@Johansson1].

It is fairly straightforward to see that ${\varepsilon}$-ASU$_2$ hash functions can be used to construct unconditionally secure authentication schemes in a natural way. Let Alice and Bob share a secret key $k$ to identify a hash function $h_k$ in a family ${\mathcal{H}}$ of ${\varepsilon}$-ASU$_2$ hash functions from ${\mathcal{M}}$ to ${\mathcal{T}}$. Alice sends her message $m$ along with $t=h_k(m)$ to Bob. Upon receiving $m$ and $t$, Bob verifies the authenticity of $m$ by comparing $h_k(m)$ with $t$. If $h_k(m)$ and $t$ are identical, then Bob accepts $m$ as authentic; otherwise, $m$ will be rejected.

Now, if 