k-way hash collisions

[kas kati]

For an ideal hash function, the complexity of finding a k-way
collision is
O(2^{(k-1)n/k}) therefore as k becomes larger, the complexity of a
k-way collision attack approaches the complexity of a pre-image
attack.

Recently, Joux showed a generic multi-collision attack for iterated
hash functions to reduce the k-way collision complexity to
O(log(k)*2^{(n/2)}). But in his attack the pre-images are not
independent. They are just combinations of block collisions of k
blocks. Here are my questions:

1. How can the formula for the complexity of finding a k-way collision
be derived?

2. Is there any hash design that allows to reduce the complexity of
k-way collision for "independent" pre-images while preserving the
complexity of the pre-image attack?

Thanks in advance for your interest.



		
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com