Eve tries to impersonate Alice and sends $m^\prime$ without knowing the key $k$, or $h_k$, the best she can do is to guess the correct tag for $m^\prime$. The probability of success in this case is $1/|{\mathcal{T}}|$. Even if Eve waits until seeing a valid message-tag pair $(m,t)$ from Alice, the probability of guessing the correct tag $t'$ for $m^\prime$ is at most ${\varepsilon}$; cf. Def. 3(b). In other words, even seeing a valid message-tag pair does not increase Eve’s success probability above ${\varepsilon}$. Therefore, by using a family of ${\varepsilon}$-ASU$_2$ hash functions with suitably chosen ${\varepsilon}$, one can achieve unconditionally secure message authentication.

In this scheme, however, a key cannot be used more than once, because a repeated use of the same key may give Eve enough information to forge a valid message-tag pair; Def. 3 does not say anything about set sizes for three message-tag pairs. Therefore, in the mode of operation considered here, WCA, a new secret key is used for each authentication. The key length for typical known families of ${\varepsilon}$-ASU$_2$ hash functions is logarithmic in the message length $\log|{\mathcal{M}}|$ [@Stinson1; @Stinson2; @Stinson3; @Stinson4; @AticiStinson; @Hugo; @Hugo1; @Johansson; @Johansson1; @Boer; @AL11], where $\log$ denotes the binary 