Skip to main content
3 of 5
deleted 87 characters in body

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):

  1. $\kappa = \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?