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$?

Improve this question
$\endgroup$
1
  • 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, 2013 at 19:40

1 Answer 1

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

Improve this answer
$\endgroup$
3
  • $\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, 2013 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, 2013 at 21:24
  • $\begingroup$ Yes, I think the elements are distinct. $\endgroup$
    – Zoidberg
    Jul 15, 2013 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.