Given two MAC schemes $\prod_1 = (keyGen_1, S_1, V_1)$ and $\prod_2=(keyGen_2, S_2, V_2)$.

$\prod_3$ runs $keyGen$ from $\prod_1$ and $\prod_2$, respectively, to obtain $(k_1, k_2)$. $\prod_3$, where $S_3 = ((k_1,k_2), (m_1,m_2))$ then runs $S_1(k_1,m_1)\rightarrow t_1$ and $S_2(k_2,m_2)\rightarrow t_2$. And obtain $t_3 := t_1||t_2$. Would $\prod_3$ be a secure MAC?

And the follow up is when $t_3:= t_1 \oplus t_2 $, would this also be a secure MAC?

My guess is that the concatenation is secure because attackers would have no way of knowing how $t_1$ and $t_2$ is generated. For the second one, my intuition tells me that adversary can somehow swap the messages and produce a valid (m,t) pair?

  • 3
    $\begingroup$ Hint: What if $\Pi_1=\Pi_2$? $\endgroup$
    – SEJPM
    Commented Apr 18, 2017 at 16:07
  • $\begingroup$ Hint: for either definition of $\Pi_3$, suppose we had a way to break the security of $\Pi_3$, would that allow us to break the security assumptions of $\Pi_1$? $\endgroup$
    – poncho
    Commented Apr 18, 2017 at 16:18
  • $\begingroup$ $S_3$ has a different input message domain than $S_1$ or $S_2$. How exactly are $m_1$ and $m_2$ created when some message $m$ is to be signed? $\endgroup$
    – Artjom B.
    Commented Apr 18, 2017 at 21:54
  • $\begingroup$ @SEJPM, if $\Pi_1=\Pi_2$, then how it is possible to construct $\Pi_3$ that is ever secure? $\endgroup$
    – Bango
    Commented Apr 22, 2017 at 22:30
  • 1
    $\begingroup$ Actually, my previous comments were wrong. I thought that if $\Pi_1=\Pi_2$ then you would sample the very same $k_1=k_2$ (which would lead to $t_3=0$). This is obviously wrong because you call the agorithms independently. $\endgroup$
    – SEJPM
    Commented Apr 23, 2017 at 17:51

1 Answer 1


In the first case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_3, m_4)$ to query the adversary $A$.

$t_1||t_2 = A(m_1, m_2)$

$t_3||t_4 = A(m_3, m_4)$

The forged MAC would be $t_1||t_4: Verify(t_1||t_4, (m_1, m_4)) \rightarrow Accept$.

In the second case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_1, m_3)$ to query the adversary $A$.

$t = t_1 \oplus t_2 = A(m_1, m_2)$

$t' = t_1 \oplus t_3 = A(m_1, m_3)$

$t_f = t \oplus t' = t_2 \oplus t_3$

The forged MAC would be $t_f: Verify(t_f, (m_2, m_3)) \rightarrow Accept$.

Another way to break the scheme is to reverse the message pair. $Verify(t, (m_2, m_1)) \rightarrow Accept$.

  • $\begingroup$ Nice, another question without any answer off the list. Welcome to cryptography! Bango, if you're still around, could you have a look if this answers your old question as it may help others (even if it may be a bit late for yourself). $\endgroup$
    – Maarten Bodewes
    Commented Apr 28, 2019 at 23:29

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.