The standard notion security for MACs is usually expressed by means of experiments like the following one (given an attacker A):

  1. $k \leftarrow \mathsf{KG}(1^\lambda)$
  2. Invoke $A^{\mathsf{TAG}_k(\cdot),\mathsf{VRFY}_k(\cdot,\cdot)}$
  3. Output $1$ if $A$ queried $(m^*,\tau^*)$ to $\mathsf{VRFY}_k(\cdot,\cdot)$ s.t. $\mathsf{VRFY}_k(m^*,\tau^*) = \mathsf{Accept}$ and $A$ didn't receive $\tau^*$ by querying $m^*$ to $\mathsf{TAG}_k(\cdot)$

Now consider the following variation to point 3: Output $1$ if $A$ gives $k'$ s.t. $k=k'$

How could I prove that a MAC unforgeable according to the first game is unforgeable according to the second game too? Is there a specific $\mathsf{MAC}(\mathsf{KG},\mathsf{TAG},\mathsf{VRFY})$ that is unforgeable according to the second game, but not according to the first one?

  • 1
    $\begingroup$ contrapositive ​ ​ $\endgroup$
    – user991
    Jul 9, 2016 at 12:28
  • $\begingroup$ Your notation seems a bit confused. Are $\kappa$ and $k$ supposed to be the same thing? And what does $= \leftarrow$ mean? $\endgroup$ Jul 9, 2016 at 17:24

2 Answers 2


I was going to make this a comment; however you asked for hint, and these are hints.

Suppose you had an Oracle that solved the second game for you; how could you use that Oracle to solve the first game?

Does that imply that a MAC where the first game is unsolvable imply that the second game is also unsolvable?


Thanks to everyone for the hints and comments. I would like to propose you my proof by contradiction and kindly ask for a further comment.

Being $\pi=(KG,TAG,VRFY)$ an uuf MAC according to the first game, we suppose that $\pi$ isn't uuf according to the second one. On the basis of this hypothesis, an attacker A can guess the secret key $k$. More formally, $A$ gives $k'$ s.t. $k=k'$.

In such a condition, given a fresh message $m^*$, $A$ can compute the authenticator $\tau^*$ without querying the oracle, because he has got the key $k$ and full knowledge of the tag function $TAG_k(\cdot)$. Therefore the initial assumption must be false.

Considering the $TAG$ function $H(k||m)$, where $H$ is a Merkle-Damgard collision-resistant hash function and $||$ indicates concatenation , we could find a specific MAC $\overline{\pi}=\overline{(KG,TAG,VRFY)}$ which is uuf according to the second game, because the attacker $A$ can't reconstruct the key $k$ it by knowing the stored hash value.

$\overline\pi$ isn't however uuf according tho the first game: given a couple $(m,\tau)$ s.t. $VRFY_k(m,\tau) = Accept$, the attacker $A$ could straightforwardly forge an authenticator $\tau^*$ for the message $m^*=m||pad_m||m'$ s.t. $VRFY_k(m^*,\tau^*)=Accept$

Thank you again, FG

  • $\begingroup$ You seem to have created two accounts. You could look into merging them so that you can accept the correct answer. $\endgroup$
    – otus
    Jul 11, 2016 at 11:21
  • $\begingroup$ I actually posted twice as a guest; can I merge the accounts anyway? $\endgroup$ Jul 11, 2016 at 12:07
  • $\begingroup$ I'm not sure. You can try. $\endgroup$
    – otus
    Jul 11, 2016 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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