k-way hash collisions

R.A. Hettinga rah at shipwright.com
Wed Dec 8 07:46:45 PST 2004


--- begin forwarded text


Delivered-To: cryptography at metzdowd.com
Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys
Date: Wed, 8 Dec 2004 07:21:18 -0800 (PST)
From: kas kati <kaskati2003 at yahoo.com>
Subject: k-way hash collisions
To: cryptography at metzdowd.com
Sender: owner-cryptography at 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 at metzdowd.com

--- end forwarded text


-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'





More information about the cypherpunks-legacy mailing list