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.

  • $\begingroup$ 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? $\endgroup$ – Jessica Bonanni Nov 9 '17 at 14:29
  • $\begingroup$ @JessicaBonanni yes. $\endgroup$ – SEJPM Nov 9 '17 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.