#

** Universal One-Way Hash Functions and their
Cryptographic Applications**

### Moni Naor
Moti Yung

### Abstract:

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:**

- Cynthia Dwork, and Moni Naor,
*An Efficient Existentially
Unforgeable Signature Scheme and Its Applications*. J. of Cryptology,Vol
11, Number 2, 1998, pp. 187-208,
Postscript
, gzipped
Postscript

Back to On-Line
Publications

Back Home