2
$\begingroup$

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.

What I found out already:
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$?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – minar Jul 12 '13 at 19:40
1
$\begingroup$

$\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} \;\;\;\;$.

$\endgroup$
  • $\begingroup$ Thanks for your answer! I think my question was a bit ambiguous. I already found out that this is the number of elements that the function can map to. I just don't know how to show that the probablility for a collision is smaller than epsilon. $\endgroup$ – Zoidberg Jul 13 '13 at 17:43
  • $\begingroup$ 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 \;$? $\;\;\;\;\;$ $\endgroup$ – user991 Jul 13 '13 at 21:24
  • $\begingroup$ Yes, I think the elements are distinct. $\endgroup$ – Zoidberg Jul 15 '13 at 17:40

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.