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.


  But I can't understand why they are different?


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.