Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 FunctionNo Birthday Attack to TCRWeaker Notion of Target Collision Resistance

share|improve this question

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.

share|improve this answer

Your Answer


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.