I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” , which compared TCR (Target Collision Resistant) and ACR (Any collision Resistant). It says

we wish to stress one important practical advantage of TCR over ACR: because $x$ must be specified before $K$ is known, birthday attacks to find collisions are not possible

I understood the definition of the notion of $TCR$, but my question is:

Why is a birthday attack is not possible?

My other questions related to the same paper:
Dependence on Keyed Hash FunctionNo Birthday Attack to TCRWeaker Notion of Target Collision Resistance

  • $\begingroup$ This question is not one that is answered with an example. $\endgroup$ – K.G. Nov 10 '13 at 9:31
  • $\begingroup$ @K.G. Then Why birthday attack is not possible? $\endgroup$ – juaninf Nov 10 '13 at 11:33

I am literally quoting the paper here. You should really try to read the paper properly first before asking questions.

In the notion of [22] the adversary does not get credit for finding any old collision. The adversary must still find a collision $M, M'$ but now $M$ is not allowed to depend on the key: the adversary must choose it before the key $K$ is known.

I can't really give an example of this, just as I can't give an example of why I can't produce light with a brick.

| improve this answer | |
  • 1
    $\begingroup$ Well, I could help you out with that brick-example by hitting it on my head until I can confirm seeing a tiny light. ;) $\endgroup$ – e-sushi Nov 10 '13 at 15:51
  • 1
    $\begingroup$ @nightcracker jaja, thank by your reply, but Why the adversary can't make a birthday attack after the $K$ key es know? $\endgroup$ – juaninf Nov 11 '13 at 16:24
  • 1
    $\begingroup$ @juaninf I just explained it in my answer. If my answer is not clear your understanding of the birthday attack is not sufficient. I'd suggest you'd do some more reading on the birthday attack/birthday paradox itself. Hint: does the birthday paradox still work if the question is "what is the chance that someone in this group has his birthday on 1st of January" rather than "what is the chance that two people in this group share a birthday?". $\endgroup$ – orlp Nov 11 '13 at 16:44
  • 1
    $\begingroup$ @nightcracker thank by your reply, I'm reading birthday attack, wikipedia say: we expect to obtain a pair of different arguments $x_1$ and $x_2$ with $f(x_1)=f(x_2)$ after evaluating the function for about $1.25\sqrt{H}$ different arguments on average. I have a doubt in relation "different arguments", Can I evaluate $f(x_1)=f(x_2); f(x_1)=f(x_3), $.... or always all arguments have be differents, in other words do not repeat $f(x_1)$ in the example? $\endgroup$ – juaninf Nov 11 '13 at 17:15

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.