1
$\begingroup$

According to Wikipedia,

$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$

Let n(p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. What if I wants my probability to be 1? In this case, $p = 1$ and $\frac{1}{1-1}$ is undefined. May I know how to find minimum number of values required to get a collision with the probability of 1 using the formula above?

$\endgroup$
  • $\begingroup$ Is this question for pure curiosity or do you need it as a building block for some protocol? $\endgroup$ – user27950 Nov 12 '16 at 9:56
5
$\begingroup$

To get a collision with probability 1, you need to hash $H+1$ distinct values. You can see that because it is possible that if you hash only $H$ values, each one might happen to hash to a unique hash output; if any reasonable sized hash function, this is extremely unlikely, but it does have a nonzero probability to happen. On the other hand, if we hash $H+1$ distinct values, we know (by the pigeon hole principle (because there are only $H$ hash outputs), that two of the inputs must hash to the same output.

|improve this answer|||||
$\endgroup$
3
$\begingroup$

The expressions on Wikipedia are probabilistic approximations and in any case look at the earlier approximation $$p\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^2/(2H)}$$ which shows you can achieve probability $1-\varepsilon$ for any $\varepsilon>0$ if you let $$e^{-n^2/(2H)}=\varepsilon$$ or $$n=\sqrt{2 H \ln (1/\varepsilon)}.$$

To guarantee a collision, you need $1+H$ distinct values by pigeonhole principle. It's much quicker to approach probability one than to guarantee it.

|improve this 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.