Amplifying
Collision-Resistance:
A Complexity-Theoretic Treatment
Ran Canetti, Ron
Rivest, Madhu
We initiate a complexity-theoretic treatment of hardness
amplification for collision-resistant hash functions, namely the transformation
of weakly collision-resistant hash functions into strongly collision-resistant
ones in the standard model of computation. We measure the level of collision
resistance by the maximum probability, over the choice of the key, for which an
efficient adversary can find a collision. The goal is to obtain constructions
with short output, short keys, small loss in adversarial complexity tolerated,
and a good trade-off between compression ratio and computational complexity. We
provide an analysis of several simple constructions, and show that many of the parameters
achieved by our constructions are almost optimal in some sense.