Beyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions

Suppose we are given a perfect

n

 + 

c

-to-

n

bit compression function

f

and we want to construct a larger

m

 + 

s

-to-

s

bit compression function

H

instead. What level of security, in particular collision resistance, can we expect from

H

if it makes

r

calls to

f

? We conjecture that typically collisions can be found in 2

(

nr

 + 

cr

 − 

m

)/(

r

 + 1)

queries. This bound is also relevant for building a

m

 + 

s

-to-

s

bit compression function based on a blockcipher with

k

-bit keys and

n

-bit blocks: simply set

c

 = 

k

, or

c

 = 0 in case of fixed keys.

We also exhibit a number of (conceptual) compression functions whose collision resistance is close to this bound. In particular, we consider the following four scenarios:

1

A 2

n

-to-

n

bit compression function making two calls to an

n

-to-

n

bit primitive, providing collision resistance up to 2

n

/3

/

n

queries. This beats a recent bound by Rogaway and Steinberger that 2

n

/4

queries to the underlying random

n

-to-

n

bit function suffice to find collisions in any rate-1/2 compression function. In particular, this shows that Rogaway and Steinberger’s recent bound of 2

(

nr

 − 

m

 − 

s

/2)/

r

)

queries (for

c

 = 0) crucially relies upon a uniformity assumption; a blanket generalization to arbitrary compression functions would be incorrect.

1

A 3

n

-to-2

n

bit compression function making a single call to a 3

n

-to-

n

bit primitive, providing collision resistance up to 2

n

queries.

1

A 3

n

-to-2

n

bit compression function making two calls to a 2

n

-to-

n

bit primitive, providing collision resistance up to 2

n

queries.

1

A single call compression function with parameters satisfying

m

 ≤ 

n

 + 

c

,

n

 ≤ 

s

,

c

 ≤ 

m

. This result provides a tradeoff between how many bits you can compress for what level of security given a single call to an

n

 + 

c

-to-

n

bit random function.