Improved Collision and Preimage Resistance Bounds on PGV Schemes

Lei Duo; Chao Li

Paper 2006/462

Improved Collision and Preimage Resistance Bounds on PGV Schemes

Lei Duo and Chao Li

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.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Contact author(s): duoduolei @ gmail com
History: 2006-12-09: revised; 2006-12-08: received; See all versions
Short URL: https://ia.cr/2006/462
License: CC BY

BibTeX

@misc{cryptoeprint:2006/462,
      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},
      url = {https://eprint.iacr.org/2006/462}
}