4
$\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)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.