Universal One-Way Hash Functions and their Cryptographic Applications

       Moni Naor      Moti Yung


We define families of Universal One-Way Hash Functions, a new primitive which enables the compression of elements in the function domain. The main property of such a family H is:  given an element x in the domain (chosen by the adversary), when h is chosen at random from H, it is computationally hard to find a different domain x' element which collides with x, i.e. h(x) =h(x').  This is sometimes called second preimage collision or target collision resistance.

We prove constructively that universal one-way hash functions exist if any 1-1 one-way functions exist.

Among the various applications of the primitive is a digital signature scheme which is existentially secure against adaptive attacks. (Previously, all provably secure signature schemes were based on the stronger mathematical assumption that  trapdoor one-way functions exist.)

Postscript , gzipped Postscript

Related On-Line Papers:

Back to On-Line Publications

Back Home