Universal One-Way Hash Functions and their
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.)
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,
Back to On-Line