**On Quantifying the Resistance of Concrete Hash Functions to Generic Multi-Collision Attacks**

*Somindu C. Ramanna and Palash Sarkar*

**Abstract: **Bellare and Kohno (2004) introduced the notion of balance to quantify the
resistance of a hash function $h$ to a generic collision attack. Motivated by
their work, we consider the problem of quantifying the resistance of $h$ to a
generic multi-collision attack. To this end, we introduce the notion of
$r$-balance $\mu_r (h)$ of $h$ and obtain bounds on the success probability of
finding an $r$-collision in terms of $\mu_r (h)$. These bounds show that for a
hash function with $m$ image points, if the number of trials $q$ is
$\Theta(rm^{(r-1)\mu_r(h)/r})$, then it is possible to find $r$-collisions with
a significant probability of success. The behaviour of random functions and
the expected number of trials to obtain an $r$-collision is studied. These results
extend and complete the earlier results obtained by Bellare and Kohno (2004) for
collisions (i.e., $r = 2$). Going beyond their work, we provide a new design
criteria to provide quantifiable resistance to generic multi-
collision attacks. Further, we make a detailed probabilistic investigation of
the variation of $r$-balance over the set of all functions and obtain support
for the view that most functions have $r$-balance close to
one.

**Category / Keywords: **foundations / hash functions, multi-collisions, birthday attacks

**Date: **received 31 Oct 2009, last revised 14 Jun 2010

**Contact author: **somindu cr at gmail com

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20100614:091208 (All versions of this report)

**Short URL: **ia.cr/2009/525

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]