# Difference between UF-CMA and UF-CMVA security

I didn't understand the difference between this two definitions, and why UFCMA is weaker than UF-CMVA. Given a $MAC=(Gen,Tag,Vrfy)$ we define

$G_{\pi,\mathcal{A}} (\lambda):$

1) $k \leftarrow \$ \{0,1\}^{\lambda}$2)$(m^*,\phi^*) \leftarrow \mathcal{A}(1^\lambda)$3) Output$1$if and only if$Tag_k (m^*)=\phi^*$and$m^*$is fresh (never queried from$\mathcal{A})$. We are assuming that$\mathcal{A}$can make$Q$queries to$Tag_k()$.$G^{UF-CMVA}_{\pi,\mathcal{A}} (\lambda):$1)$k \leftarrow \$\{0,1\}^{\lambda}$

2) $(m^*,\phi^*) \leftarrow \mathcal{A}^{Tag_k(),Vrfy_k()}(1^\lambda)$

3) Output $1$ if and only if $Vrfy_k (m^*,\phi^*)=Accepted$ and $m^*$ is fresh (never queried from $\mathcal{A})$. We are assuming that $\mathcal{A}$ can make $Q_T$ queries to $Tag_k()$ and $Q_v$ queries to $Vrfy_k()$.

In pratice this new game is identical to the precedent game but here $\mathcal{A}$ has also access to the oracle $Vrfy$. But I can't understand why they are different and why if the tag $\phi$ is unique (that's for every key $k$, there exist a $\phi$ for every message i.e the algorithm $Tag$ is deterministic) the two Games are identical.

Why if the tag $\varphi$ is unique the two Games are identical?
If your Tag algorithm is deterministic, then verifying a tag-message-pair is actually just re-computing the tag for the message and checking if the provided and the re-computed tags match. So in this case $\operatorname{Vrfy}_k(m,\tau):=\operatorname{Tag}_k(m)\stackrel?=\tau$. So I hope now you see how step 3 is identitical in both games if $\operatorname{Tag}$ is deterministic.
Because there are MAC algorithms for which $\operatorname{Tag}$ works non-deterministically, that is with large probability two tags for the same message will differ. Now you can no longer check whether a tag-message-pair is valid as above, you need a more complex verification algorithm.
As a contrived example consider the scheme $M$ which is HMAC with the following modification for the tag-generation: First you generate a random 128-bit string and prepend it to the message, then you run the modified message through the HMAC and return the concatenation of the random string and the HMAC-tag. Verification now works by taking the prepended random string and prepending it to the message before feeding it into the HMAC oracle.
• Ok, so the problem is that if Tag is probabilistic it can assume different values with certain probability, and so the Adversary can not verify in poly-time if $\tau$ is a possible Tag for the message. Is correct? – Jessica Bonanni Nov 9 '17 at 14:29