3
$\begingroup$

I am going through some of my notes from class (About Information Security) and I'm stuck understanding how my teacher got this result. The question is:

How many collisions would you expect to find in the following cases?

a) Your hash function generates a 12-bit output and you hash 1024 randomly selected messages.

b) Your hash function generates an n-bit output and you hash m randomly selected messages.

The teacher's only answered a) like so:

We expect to find one collision every $2^{n/2}$ hashes. There are $2^{(n/2) * 2} = 2^n$ comparisons. Since the output is 12-bit the answer is $2^{10 * 2}/2 ^{12} = 2^{8} = 256$ collisions.

However I don't quite understand how he got this?

I get that the expected number of collision after n hashes would be $2^{n/2}$. But the rest doesn't make sense to me. I mean if the output is 12 bits (4096 arrangements), why would we expect to get 256 collision after only hashing 1024 messages (1/4 of the possible outputs)?

$\endgroup$
2
$\begingroup$

I suspect you are misrepresenting what your professor actually said.

Since I'm not certain exactly what he said, here is how I would explain it:

  • With 1024 outputs, there are $\binom{1024}{2} \approx 1024^2/2$ pairs of outputs.

  • For each pair of output, that pair has a $2^{-12}$ probability of being a collision (that is, those two outputs being exactly the same).

  • Hence, the expected number of collisions would be about $1024^2/2 \times 2^{-12} = 128$

The exact expected number would depend how you count a multiway collision (where 3 or more outputs have the same value); it turns out that, if you count it right, $\binom{1024}{2} 2^{-12}$ is the correct answer.

$\endgroup$

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.