Weaker Notion of Target Collision Resistance

Question

I'm reading the paper “Collision-Resistant Hashing? Towards Making UOWHFs Practical” which states:

While it might be easy to find a collision $M,M'$ in $F_K$ by making both $M,M'$ depend on $K$ (Any Collision Resistance), the adversary may be unable to find collisions if she is forced to commit to one point of the collision before seeing $K$. We call this weakened notion of security target collision resistance TCR

nb: $K$ is a key used to a hash function $F$.

My question is: Why then TCR is a weakened notion if the article says that it is easier to find a collision $M,M'$ than TCR?

_{My other questions related to the same paper:
Dependence on Keyed Hash Function • No Birthday Attack to TCR • Weaker Notion of Target Collision Resistance}

Answer 1

We often rank cryptographic problems according to how hard they are. One problem is not harder than another problem if an algorithm that solves the second problem can easily be turned into an algorithm that solves the first problem.

Your question considers two issues: how hard the adversary's job is, and the strength of our assumption. If one problem is not harder than another problem, then if we assume that the first problem is hard, we must also assume that the second problem is hard. However, if we assume that the second problem is hard, the first problem may still be easy.

Since assuming that the first problem is hard has more implications than assuming the second problem is hard, we say that the first assumption is stronger than the second assumption, and correspondingly that the second assumption is weaker.

Any adversary against TCR is trivially an adversary against collision resistance, so TCR is not harder than collision resistance. Therefore, we say that TCR is a weaker notion than collision resistance.