So let any secure MAC (message authentication code) be given.

Intuitively, I think it is clear that the probability of getting the same tag on two different messages is very small, i.e. negligible. I want to prove this statement mathematically.

How can we

  1. formulate this in an exact manner (because, negligible in what? I guess negligible in $|k|$, where $k$ is the chosen key - I am not sure about this)

  2. (once we have a precise formulation) prove this statement?

Supposing that this probability is not negligible, we'll have to construct a PPT adversary $\mathcal A$ that, somehow, is able to "beat" the system (which would be in contradiction with the fact that the MAC is secure).

  • $\begingroup$ If you'll have to construct a PPT adversary, then you'll only be able to show this for $\hspace{1.25 in}$ PPT-computable sequences of pairs of messages. $\:$ $\endgroup$
    – user991
    Nov 18 '12 at 6:06
  • $\begingroup$ The term neglible usually refers to some security parameter (which often is the key length). The same term is used in the definition of "secure" for your MAC, which will give you the point of attack. (Also, welcome to Cryptography Stack Exchange.) $\endgroup$ Nov 19 '12 at 14:37

Is this a homework problem?

Here's a hint: Suppose that the probability of getting the same tag on two different messages is $p$. Show how to construct an adversary that breaks the MAC (i.e., forges a valid tag), and that has success probability $p$. Assuming the MAC is secure, what can you conclude about the possible range of values for $p$?

  • $\begingroup$ It's not a homework problem. By the way, I don't see the relevance of such a comment/question. $\endgroup$
    – Dorothy
    Nov 18 '12 at 22:12
  • 2
    $\begingroup$ @Dorothy, because this looked a lot like a homework problem, because I'm not interested in solving other people's homework problems for them -- and because doing so would be a disservice to them, because the entire point of homework is to learn how to solve the question on your own, which you can't get by reading other people's solutions. You can read the thread on meta. One suggestion: I would recommend revising the question to show what you've tried already and where you've gotten stuck. My answer should give you a good direction to try... $\endgroup$
    – D.W.
    Nov 18 '12 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.