5
$\begingroup$

Say we have a hash function that produces $n$ bit outputs. From the birthday problem that after around $\sqrt{2^n}$ different inputs to the has function, we can expect a collision.

Say instead that we have $m$ outputs. How many collisions can we expect in those $m$ outputs?

If there are $k$ inputs that all have the same output, we say there are $\binom{k}{2}$ collisions.

$\endgroup$
8
$\begingroup$

The expected number of collisions (assuming that the hash function can be modeled as a random function) is precisely $2^{-n}\binom{m}{2}$; that is, the expected number of pairs of values $x \ne y$ with $H(x) = H(y)$ (and so, to answer Ricky's question, $H(x) = H(y) = H(z)$ would count as three collisions).

The reasoning is the obvious one; there are $\binom{m}{2}$ separate pairs, and each pair has a probability $2^{-n}$ of colliding (and hence has an expected number of collisions of $2^{-n}$), and the expected sum of a set of probabilistic values is the sum of each individual value's expectation. The probabilities are not independent (for example, if $H(x)=H(y)$ and $H(y)\ne H(z)$, we know that $H(x) \ne H(z)$); it turns out that the expected sum doesn't depend on independence.

$\endgroup$
  • $\begingroup$ @mikeazo Does that mean that these tables are inaccurate in their estimates of the p=50% scenario or am I misunderstanding what these tables represent. It seems to me if the p=0.5 should occur when number of "perfectly random and normally distributed hashes" is 2^(n/2) then the 50% column should read: 256 for 16 bit hashes, 65536 for 32 bit hashes and so on? (Meta question: should I be raising this as a new question? I know my question is different but It just seemed really relevant to what's discussed here). $\endgroup$ – Iam Nick Jan 11 '16 at 16:04

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.