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