Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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

 
discard

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

Browse other questions tagged or ask your own question.