Welcome to the resource topic for 2011/630
Title:
Indifferentiability Security of the Fast Wide Pipe Hash: Breaking the Birthday Barrier
Authors: Dustin Moody, Souradyuti Paul, Daniel Smith-Tone
Abstract:A hash function secure in the indifferentiability framework (TCC 2004) is able to resist all meaningful generic attacks. Such hash functions also play a crucial role in establishing the security of protocols that use them as random functions. To eliminate multi-collision type attacks on the MD mode (Crypto 1989), Lucks proposed widening the size of the internal state of hash functions. More specifically, he suggested that hash functions h:{0,1}*->{0,1}^n use underlying primitives of the form C:{0,1}^a → {0,1}^{2n} (Asiacrypt 2005). The Fast Wide Pipe (FWP) hash mode was introduced by Nandi and Paul at Indocrypt 2010, as a faster variant of Lucks’ Wide Pipe mode. Despite the higher speed, the proven indifferentiability bound of the FWP mode has so far been only up to the birthday barrier of n/2 bits. The main result of this paper is the improvement of the FWP bound to 2n/3 bits (up to an additive constant). The 2n/3-bit bound for FWP comes with two important implications. Many popular hash modes use primitives with a=2n, that is C:{0,1}^{2n}->{0,1}^{2n}. For this important case, the FWP becomes the only mode to achieve indifferentiability security of more than n/2 bits; thus we solve a longstanding open problem. Secondly, among n-bit hash modes with a>2n, the FWP mode has the highest rate among all modes which have beyond-birthday-barrier security. To obtain the bound of 2n/3 bits, we follow the usual technique of constructing games with simulators, with certain BAD events to distinguish between the games. However, we introduce some novel ideas. In designing the BAD events, we used multi-collisions in addition to collisions. We also allowed the query-response graphs, maintained by the simulators, to grow for two phases every iteration, rather than just one phase. Finally, our carefully chosen set of sixteen BAD events establish an isomorphism of simulator graphs, from which the 2n/3-bit bound follows. We also provide evidence that extending the bound beyond 2n/3 bits may be possible if we allow the simulator-graph to grow for three (or more) phases every iteration. Another noteworthy feature of our proof – that may be of independent interest – is that we work with only three games rather than a long sequence games.
ePrint: https://eprint.iacr.org/2011/630
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 .