Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  minar Jul 12 '13 at 19:40

1 Answer 1

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

share|improve this answer
    
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. –  Zoidberg Jul 13 '13 at 17:43
    
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 \;$? $\;\;\;\;\;$ –  Ricky Demer Jul 13 '13 at 21:24
    
Yes, I think the elements are distinct. –  Zoidberg Jul 15 '13 at 17:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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