## The gap between collision-resistant functions and WUFs

### Ilya Mironov

### Ph.D. student, Applied Cryptography Group,
Computer Science Dept., Stanford.

A family of collision-resistant functions (CRFs) is one of the basic
primitives of the modern cryptography. Unfortunately, they are hard to
construct both in practice (the compression function of a CRF hopeful
MD5
was broken in 1996) and in theory (they cannot be built from one-way
functions via a black-box construction). As a useful alternative to
CRFs a
notion of universal one-way hash functions (WUFs) was proposed in
1989.

Despite their theoretical attractiveness WUFs suffer from a seemingly
technical obstacle to their universal acceptance: any practical
construction
of a family of WUFs has a key length that grows with the message
length.
The
Merkle-Damgaard construction that yields a family of CRFs with a
constant
key length is insecure when applied to WUFs.

In this talk we will see how to apply the Merkle-Damgaard construction
to
functions that lie between CRFs and WUFs. The best construction
for families of WUFs (due to Shoup) and its optimality result will be
presented.

Gates 4B, 10/31/00, 4:45 PM