Aristeidis Tentes

Compression from Collisions, or why CRHF Combiners have a Long Output

AUTHORS: Krzysztof Pietrzak

A black-box combiner for collision resistant hash functions
(CRHF) is a construction which given black-box access to two hash functions
is collision resistant if at least one of the components is collision

In this paper we prove a lower bound on the output length of black-box
combiners for CRHFs. The bound we prove is basically tight as it is
achieved by a recent construction of Canetti et al [Crypto'07]. The best
previously known lower bounds only ruled out a very restricted class of
combiners having a very strong security reduction: the reduction was required
to output collisions for both underlying candidate hash-functions
given a single collision for the combiner (Canetti et al [Crypto'07] building
on Boneh and Boyen [Crypto'06] and Pietrzak [Eurocrypt'07]).

Our proof uses a lemma similar to the elegant \reconstruction lemma" of
Gennaro and Trevisan [FOCS'00], which states that any function which
is not one-way is compressible (and thus uniformly random function must
be one-way). In a similar vein we show that a function which is not collision
resistant is compressible. We also borrow ideas from recent work by
Haitner et al. [FOCS'07], who show that one can prove the reconstruction
lemma even relative to some very powerful oracles (in our case this
will be an exponential time collision- nding oracle).