Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

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

(a) 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)

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

share|improve this question
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

1 Answer

up vote 1 down vote

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

share|improve this answer
It's not a homework problem. By the way, I don't see the relevance of such a comment/question. – Dorothy Nov 18 '12 at 22:12
1  
@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... – D.W. Nov 18 '12 at 22:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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