Skip to main content
3 of 5
fixed missing exponentiations
SEJPM
  • 46.4k
  • 9
  • 102
  • 210

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

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.