Title: On the Design of Provably-Secure Cryptographic Hash Functions
Abstract: Recently, formal complexity-theoretic treatment of cryptographic hash functions was suggested. Two primitives of Collision-free hash functions and Universal one-way hash function families have been defined. The primitives have numerous applications in secure information compression, since their security implies that finding collisions is computationally hard. Most notably, Naor and Yung have shown that the most secure signature scheme can be reduced to the existence of universal one-way hash (this, in turn, gives the first trapdoor-less provably secure signature scheme).