Team for Research in
Ubiquitous Secure Technology

Citation
"• On the impossibility of efficiently combining collision resistant hash functions.". D. Boneh and X. Boyen (eds.), Crypto, 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.

Electronic downloads

• http://crypto.stanford.edu/~xb/crypto06b/blackboxhash.pdf

• HTML

   <a
  href="http://www.truststc.org/pubs/594.html"
  ><i>•	On the impossibility of
  efficiently combining collision resistant hash
  functions.</i></a>, D. Boneh and X. Boyen
  (eds.), Crypto, 2006.

• Plain text

   "•	On the impossibility of efficiently
  combining collision resistant hash functions.". D.
  Boneh and X. Boyen (eds.), Crypto, 2006.

• BibTeX

  @proceedings{BonehBoyen06_OnImpossibilityOfEfficientlyCombiningCollisionResistant,
      title = {•	On the impossibility of efficiently combining
                collision resistant hash functions.},
      editor = {D. Boneh and X. Boyen},
      organization = {Crypto},
      year = {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. },
      URL = {http://www.truststc.org/pubs/594.html}
  }
  

Posted by Jessica Gamble on 16 Mar 2009.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.