On the impossibility of efficiently combining collision resistant hash functions
Authors: D. Boneh and X. Boyen
Abstract:
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.
Reference:
In proceedings of Crypto '06, LNCS 4117, pp. 570-583, 2006
Full paper: pdf