# Secure MAC implies that probability of same tags on different messages is negligible

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).

-
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. $\:$ –  Ricky Demer Nov 18 '12 at 6:06
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.) –  Paŭlo Ebermann Nov 19 '12 at 14:37

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$?