Daniel Wichs
New York University

On the Impossibility of Efficiently Combining Collision Resistant Hash

Let H1,H2 be two hash functions. We wish to construct a new hash function H
that is collision resistant if at least one of H1 or H2 is collision resistant.
Concatenating the output of H1 and H2 clearly works, but at the cost of doubling
the hash output size. We ask whether a better construction exists, namely, can
we hedge our bets without doubling the size of the output? We take a step
towards answering this question in the negative --- we show that any secure
construction that evaluates each hash function once cannot output fewer bits
than simply concatenating the given functions.

Authors: Dan Boneh (Stanford University) and Xavier Boyen (Voltage Inc.)