MAC question i got in a test, would like your opinion on my answer

Question

Given a MAC secure scheme $(\text{Gen}, \text{Mac}, \text{Vrfy})$, a new scheme is suggested:

• $\text{Gen}' \rightarrow \text{Gen} = (pk_1, sk_1), \text{Gen} = (pk_2,sk_2)$
• $\text{Mac}'(m) = (\text{Mac}_{sk_1}(m),\text{Mac}_{sk_2}(m)) = (s_1,s_2)$
• $\text{Vrfy}'(m,(s_1,s_2)) = \text{Vrfy}_{sk_1}(m,s_1) == 1 \, || \, \text{Vrfy}_{sk_2}(m,s_2) == 1$

I proved the security of this scheme with the following reduction: given an adversary that beats this scheme $A'$, we look at the following adversary $A$ with access to oracle $\text{Mac}_{sk}(\ast)$:

1. Run $A'$.
2. When $A'$ sends a request to his $\text{Mac}'()$ oracle, ask your oracle and return $(\text{Mac}(m),\text{Mac}(m))$.
3. When $A'$ returns $(m,(s_1,s_2))$, if $\text{Vrfy}_{pk}(m,s_1) == 1$ return $(m,s_1)$, otherwise return $(m,s_2)$.

If $A'$ beats $\text{Mac}'$ $\rightarrow$ $\text{Vrfy}_{pk}(m,s_1) == 1 \, || \, \text{Vrfy}_{pk}(m,s_2) == 1$ $\rightarrow$ $A$ beats $\text{Mac}$.

Do you think this proof is sufficient?

Answer 1

No, your "proof" is not sufficient, as it is wrong. First of all, when talking about public keys, you are probably talking about (secure) digital signature schemes? A MAC scheme only uses private keys. Either the exercise from your test is wrong or uses non-traditional names on purpose (or you mixed up few things, in which case you should have another look into the material, before solving this exercise).

Assuming you are talking about digital signatures then your reduction is still wrong.

In order to relate the success probability of your construction A to that of the given $A'$, $A'$ needs to be simulated by A with inputs which are distributed as in the game $A'$ "expects"! (Note: "Expects" is just for intuition. Formally the success probability is simply just defined with respect to the distribution from the game.)

For signatures this "expected" game is usually the EUF-CMA game, which I assume from now on. There, first, $A'$ obtains two public keys $(pk_1,pk_2)$. This step is missing in your description but important. In the answers of her oracle queries $A'$ then "expects" to get signatures which verify according to $(pk_1,pk_2)$. When considering your second step, the signatures would be valid for the public key $(pk,pk)$, where $pk$ is the public key $A$ obtains. However: The tuple $(pk,pk)$ is distinguishably differently distributed compared to $(pk_1,pk_2)$ (which results from two independent runs of $\text{Gen}$). In particular, $A'$ may just stop when being fed with two identical public keys, while it may does something meaningful when $pk_1 \neq pk_2$. For such an $A'$ your simulation in $A$ would always fail.

To overcome this problem, you need to think of a slightly smarter strategy of providing a pair of public keys and answering the oracle queries. Your public key has to be included somehow. What can you do, to generate another one such that you are able to answer signature queries? I think, this may help you to solve your exercise more properly. Also, I'd recommend that you should do a more detailed proof which fleshes out all the details.

Answer 2

Thought about this more, and the reason this proof is wrong is simply due to the difference in distributions.

the adversary A' is built such that given two random pairs of sk-pk keys, it beats the scheme in a non-negligible way.

what i present to the A' distributes very differently (same sk-pk for both pairs), so the probability in which A' will beat the scheme might not be the same.

thanks everyone for the answers!