International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Improved Collision and Preimage Resistance Bounds on PGV Schemes

Lei Duo
Chao Li
Search ePrint
Search Google
Abstract: Preneel, Govaerts, and Vandewalle[14](PGV) 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 Shrimpton[3](BRS) 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.
  title={Improved Collision and Preimage Resistance Bounds on PGV Schemes},
  booktitle={IACR Eprint archive},
  note={ 13491 received 5 Dec 2006, last revised 8 Dec 2006},
  author={Lei Duo and Chao Li},