# Probability for collisions of a one-way compression function

Given a one-way compression function $h:\{0,1\}^n \rightarrow \{0,1\}^m$ and an attacker that picks $x_1 \ldots x_t \in \{0,1\}^n$ (uniformly distributed), I have to show that the probability to find a collision in the picked elements is smaller than $\epsilon$ if $m > log(\frac{t^2}{2 \epsilon})$.
Assumption: $h$ is surjective and has the same number of inverse images for each image.

Because a binary alphabet is used, I have to show that the probability is smaller than $\epsilon$ if there are at least $\frac{t^2}{2 \epsilon}$ elements that the compression function can map to. And because I want to find a collision between two elements, there are ${t \choose 2} \le \frac{t^2}{2}$ possible combinations for a collision pair in the set of picked elements.

Question:
How can I go on from here and how do I handle the $\epsilon$?

• From the birthday paradox page on wikipedia, en.wikipedia.org/wiki/Birthday_problem, you should be able to solve your problem. Look at $p(n;d)$. The only issue is that they give an approximation of the probability instead of an upper bound, so you will need some work to get it in the form you desire. Jul 12, 2013 at 19:40

$\left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \:$ is the number of elements that the compression function can map to.
If $\: m > \operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right) \:$ then $\;\; \left|\hspace{.01 in}\operatorname{Range}(h)\hspace{.01 in}\right| \: = \: 2^m \: > \: 2^\left(\operatorname{log}_{\hspace{.01 in}2}\left(\hspace{-0.03 in}\frac{t^2}{2\cdot \epsilon}\hspace{-0.04 in}\right)\right) \: = \: \frac{t^2}{2\cdot \epsilon} \;\;\;\;$.
• Are the elements $\:x_1,...,x_t\:$ necessarily distinct? $\;\;$ If no, does it count as a collision $\hspace{1.24 in}$ when $\: h(x_i) = h(x_j) \:$ and $\; x_i = x_j \:\:$ but $\: i\neq j \;$? $\;\;\;\;\;$