On the Impossibility of Efficiently Combining Collision Resistant Hash Functions

By Dan Boneh and Xavier Boyen.

In Advances in Cryptology (CRYPTO 2006), volume 4117 of Lecture Notes in Computer Science, pages 570-583. Springer, 2006.

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.

Material

- published paper (PS) (PDF) (also accessible from the publisher) © IACR
- authors' version (PS) (PDF)
- presentation slides (HTML)

Reference

@InProceedings{Boneh+Boyen:CRYPTO-2006:blackboxhash,
  author = {Dan Boneh and Xavier Boyen},
  title = {On the Impossibility of Efficiently Combining Collision Resistant Hash Functions},
  booktitle = {Advances in Cryptology---CRYPTO 2006},
  series = {Lecture Notes in Computer Science},
  volume = {4117},
  pages = {570--583},
  publisher = {Berlin: Springer-Verlag},
  year = {2006},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/crypto06b/}}
}