Paper 2006/462

Improved Collision and Preimage Resistance Bounds on PGV Schemes

Lei Duo and Chao Li


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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
duoduolei @ gmail com
2006-12-09: revised
2006-12-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lei Duo and Chao Li},
      title = {Improved Collision and Preimage Resistance Bounds on PGV Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2006/462},
      year = {2006},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.