Collision-Resistant Compression Functions based on Simple Idealized
Building Blocks

Abstract:
We consider the problem of domain and range extension of a public random function. Our main emphasis goes to the construction of collision resistant compression functions. The challenge then is to get good collision resistance for the compression function while keeping the number of calls to the public random function low.

Specifically, we exhibit a 2n-to-n bit compression function based on three calls to n-to-n bit public random functions, as well as a 3n-to-2nbit compression function based on a single call to a 3n-to-n bit public random function. For both compression functions the collision resistance is close to what one would expect/hope for given the birthday bound.

Part of this work is jointly with Thomas Shrimpton

"STAM Martijn" is mentioned on: Home | Participants