[16515] in cryptography@c2.net mail archive
k-way hash collisions
daemon@ATHENA.MIT.EDU (kas kati)
Wed Dec 8 10:31:47 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 8 Dec 2004 07:21:18 -0800 (PST)
From: kas kati <kaskati2003@yahoo.com>
To: cryptography@metzdowd.com
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@metzdowd.com
