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