The mac-forge security game for mac schemes looks like this:

  1. $k \leftarrow \operatorname{Gen}(1^n)$;
  2. $(m,t) \leftarrow A^{\operatorname{MAC}_k(⋅)}(1^n)$;
  3. Let $Q$ denote the set of all queries that $A$ asked to its oracle;
  4. The output of the experiment is defined to be $1$ if and only if $\operatorname{Verif}_k(m,t)=1$ and $m \notin Q$.

So, in this experiment the adversary has acces to a $MAC(.)$ oracle. But let's consider another experiment that where the adversary also has acces to a verify oracle, but otherwise the experiment is the exact same. Let's call the experiment mac-forge*.

If we consider a mac scheme that is secure with respect to both these definitions, can we then make a new scheme from it, that is secure for mac-forge, but not mac-forge*?

I suspect something strange should be done to the verify function, but I really don't know what.


If I construct vrfy* like:

vrfy*k(m,t) = if tag has correct length, just Mac(m), and if Mac(m) = t

, output true, elif if Mac(m) != t output false
if tag is smaller than it should be, and has length i, output the i'th bit of the key

  • $\begingroup$ Hint: Can you somehow have the verify function leak information without impeding correctness? $\endgroup$
    – SEJPM
    Mar 23, 2021 at 8:21
  • $\begingroup$ SEJPM: I was thinking maybe something regarding also letting the verify do a mac? $\endgroup$ Mar 23, 2021 at 8:43
  • $\begingroup$ Is there perhaps some (static?) secret the verification function could leak one bit at a time? $\endgroup$
    – SEJPM
    Mar 23, 2021 at 11:05
  • 1
    $\begingroup$ Ahh, an adversary is always assumed to know everything about the scheme in question besides the things that are dynamically generated and not handed to them, which is usually only the key. $\endgroup$
    – SEJPM
    Mar 23, 2021 at 11:16
  • 1
    $\begingroup$ I don't see how vrfy* meets the mac-forge security game; the attacker can submit as his guess an arbitrary message and a one bit tag; if bit 1 of the key happens to be 1 (probability 0.5), then he wins (and I believe the rules of the game is he wins if his guess is correct with nonneglible probability) $\endgroup$
    – poncho
    Mar 23, 2021 at 13:14

1 Answer 1


Using your terminology, if a scheme is secure in the mac-forge game then it is also secure in the mac-forge* game. The formal proof is a bit fussy I can sketch the main idea.

First, without loss of generality, assume that in the mac-forge* game the adversary never queries the verification oracle on $(m,t)$ that was a result of a prior MAC query. This is without loss of generality because we already know what the verification oracle will answer (true) on such an input, so there is no need to query.

Claim: If the MAC scheme is secure in mac-forge then in the mac-forge* game the verification oracle will answer false to all queries.

The proof idea is as follows: Suppose we have an adversary $A$ who breaks security of the mac-forge* game. We will use it to construct a new adversary that breaks the security of the mac-forge game. Suppose $A$'s $i$th query to the verification oracle is the first one that returns true. Construct a new adversary $A^*_i$ which does the following in the mac-forge game:

  • run $A$
  • whenever $A$ makes a MAC query, make the same MAC query in the mac-forge game and relay the result back to $A$
  • when $A$ makes verification queries 1 through $i-1$, give the answer false to $A$
  • when $A$ makes the the $i$th verification query $(m,t)$, halt with output $(m,t)$.

So $A^*_i$ plays in the mac-forge game (it never makes verification oracle queries). If $A$'s $i$th verification query really was the first one that returns true, then:

  • $A^*_i$ provides a view for $A$ that is identical to when $A$ plays the mac-forge* game (identical until we terminate $A$ early)
  • $A^*_i$ halts with a valid forgery.

So $A^*_i$ breaks the mac-forge security of the scheme.

This is just a sketch, and it somewhat assumes that it is always the $i$th verification query that works. In the real proof, you would choose $i$ uniformly at random and incur a loss in concrete security.

  • 2
    $\begingroup$ I'm pretty sure the question is a homework assignment that tries to have the student come up with the separation between UF-1 and UF-M as defined in this paper (and proven to be distinct for the non-strong case) where the availability of a verification oracle was proven to be a stronger definition than only having one verification query at the end. $\endgroup$
    – SEJPM
    Mar 25, 2021 at 15:55
  • $\begingroup$ OK, I see that the guard condition in the top post is "$m$ never queried to MAC", not "$(m,t)$ never the result of MAC query". Also the construction in that paper does not use a canonical verification algorithm. Seems like a wicked homework assignment. $\endgroup$
    – Mikero
    Mar 25, 2021 at 16: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.