0
$\begingroup$

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 Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance

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

1 Answer 1

Reset to default
4
$\begingroup$

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
$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 17:15

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.