Welcome to the resource topic for 2009/525
Title:
On Quantifying the Resistance of Concrete Hash Functions to Generic Multi-Collision Attacks
Authors: Somindu C. Ramanna, 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.
ePrint: https://eprint.iacr.org/2009/525
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .