I'm studying about MAC and followings are definition of secure MAC.

(This is Def 4.2 and Def 4.3 of "J.Katz and Y.Lindell-Introduction to Modern Cryptography")

enter image description here

enter image description here

enter image description here

I want to prove this statement

"There exists a MAC that is secure(Def 4.2) but is not strongly secure(Def 4.3)

Thank you.

  • $\begingroup$ Hint: Let $Q_w$ and $Q_s$ denote the "weak" and "strong" versions of $Q$. When would $m \in Q_w$ but $(m,t) \notin Q_s$? How could you arrange that? (Hint 2: You should probably assume the existence of a strongly secure MAC, since AFAIK that in itself is still an unproven conjecture unless our definition of a MAC is broad enough to admit something like Carter-Wegman + OTP. Then find a way to weaken that MAC.) $\endgroup$ Apr 11, 2019 at 7:04
  • $\begingroup$ See crypto.stackexchange.com/questions/44535/… $\endgroup$
    – hakoja
    Apr 11, 2019 at 8:40
  • $\begingroup$ Or very similarly crypto.stackexchange.com/questions/43169/… (note that this question is talking about the integrity of ciphertexts of an encryption scheme, not of the security of MACs, but the reasoning/main idea given in the answer is the same in both cases) $\endgroup$
    – hakoja
    Apr 11, 2019 at 8:43


Browse other questions tagged or ask your own question.