Return to 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 first bit of m is 0, run Mac(m) (exluding the first bit). if it outputs t return true.  
   if first bit of m is 1, output true if m = k, else 0

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

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.

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 first bit of m is 0, run Mac(m) (exluding the first bit). if it outputs t return true.  
   if first bit of m is 1, output true if m = k, else 0

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

1. $k \leftarrow \operatorname{Gen}(1n)$;
2. $(m,t) \leftarrow A \operatorname{MAC}_k(⋅)(1n)$;
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, int 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.

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.