Skip to main content
2 of 5
At Crypto.SE, “thank you” works via upvoting and accepting answers.
e-sushi
  • 18.1k
  • 12
  • 85
  • 235

MAC unforgeability and secret key guessing

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

$$ \kappa = \leftarrow KG(1^\lambda) $$ $$ Invoke \space A^{TAG_k(\cdot),VRFY_k(\cdot,\cdot)} $$ $$ Output \space 1 \space if \space A \space queried \space (m^*,\tau^*) \space to \space VRFY_k(\cdot,\cdot) \space s.t. \space VRFY_k(m^*,\tau^*) = Accept \space and \space A \space didn't \space receive \space \tau^* \space by \space querying \space m^* \space to \space TAG_k(\cdot) $$

Now consider the following variation to point 3: $$Output \space 1 \space \space if \space A \space gives \space k' \space s.t. \space 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 $MAC(KG,TAG,VRFY$) that is unforgeable according to the second game, but not according to the first one?