I'm reading a notion Any Collision Resistance for Hash Functions. In the lecture define a collision finder CF.

CF is said to $(t,\epsilon)$-break the family of hash functions $F_K$ if the running time is at most $t$, and the probability that CF, on input K, outputs a collision $M,M'$ for $F_K$ is at least $\epsilon$. Here the probability is take over $K$ (key space) and CF's random coins.

My question is What does it means that the probability is take over $K$ and CF's random coins?


CF is a randomized algorithm with input $K$. As a randomized algorithm, it is allowed to do random decisions in its calculations – this can be thought of flipping a coin. The results of these coin-tosses (i.e. a list of heads and tails) – can be thought as another "input".

For each key $K$ and each list of coins, the algorithm either finds a collision or doesn't.

Now we assume some random distribution of both (usually a uniform distribution of the keys, and an uniform distribution of each of the coin tosses), and can determine the probability of the success.

This probability is what is meant in your definition.

For example, if you have a hash function family $F_K$ with $2^{50}$ keys, a (quite dumb, but fast) algorithm would be to toss 200 coins to generate two 100-bit strings and output them. They either are a collision or are not, and it depends both on the key and the tossed coins whether it works. Calculate the number of combinations of "good" keys and tosses on one hand, divide by the total number of keys times the total number of possible coin toss results (this is $2^{50} · 2^{200}$). Assuming that for half of the keys exactly one collision (of 100-bit inputs) exists (and for the other half of the keys there is none), we would have $$P(\text{algorithm finds collision}) = \dfrac{2^{49} · 2 }{2^{50} · 2^{200}} = \frac{1}{2^{200}}.$$ (This is 2 instead of 1 in the first fraction, because if $F_K(a) = F_K(b)$, we also have $F_K(b) = F_K(a)$, and the algorithm could find any of them.)

| improve this answer | |

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.