[Resource Topic] 2006/462: Improved Collision and Preimage Resistance Bounds on PGV Schemes

Welcome to the resource topic for 2006/462

Improved Collision and Preimage Resistance Bounds on PGV Schemes

Authors: Lei Duo, Chao Li


Preneel, Govaerts, and Vandewalle14 considered 64 most basic ways to construct a hash function from a block cipher, and regarded 12 of those 64 schemes as secure. Black, Pogaway and Shrimpton3 provided a formal and quantitative treatment of those 64 constructions and proved that, in black-box model, the 12 schemes ( group-1 ) that PGV singled out as secure really are secure. By step ping outside of the Merkle-Damgard[4] approach to analysis, an additional 8 (group-2) of the 64 schemes are just as collision resistant as the first group of schemes. Tight upper and lower bounds on collision resistance of those 20 schemes were given. In this paper, those collision resistance and preimage resistance bounds are improved, which shows that, in black box model, collision bounds of those 20 schemes are same. In Group-1 schemes, 8 out of 12 can find fixed point easily. Bounds on second preimage, multicollisions of Joux[6], fixed-point multicollisons[8] and combine of the two kinds multicollisions are also given. From those bounds, Group-1 schemes can also be deviled into two group.

ePrint: https://eprint.iacr.org/2006/462

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 .