MathOverflow is a question and answer site for professional mathematicians. 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

Given a hash function H and a fixed permutation pi of the digest set. Consider "collisions" of the form H(x) = pi(H(x')). How is resistance against this kind of collision related to the other commonly studied forms of collision resistance?

share|cite|improve this question
I can't think of anything so far that isn't shallow. Certainly given $H$ you can construct a $\pi$ for which you can find a permuted collision, and given any $\pi$ other than the identity you can modify $H$ (by composing it with another permutation) to produce a collision-resistant hash function that has a $\pi$-collision. So if $H$ or $\pi$ is chosen adversarially, you're in trouble. Presumably for most hash functions this works in practice if $H$ and $\pi$ are chosen independently in some sense, but I don't see how to formalize this offhand. For example, what if $\pi$ is chosen at random? – Henry Cohn May 5 '13 at 16:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.