Constructing a mac scheme secure to regular definition but insecure to special case

Question

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.

Edit

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

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.