International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Non-Trivial Black-Box Combiners for Collision-Resistant Hash-Functions don't Exist

Authors:
Krzysztof Pietrzak
Download:
URL: http://eprint.iacr.org/2006/348
Search ePrint
Search Google
Abstract: A $(k,\ell)$-robust combiner for collision-resistant hash-functions is a construction which from $\ell$ hash-functions constructs a hash-function which is collision-resistant if at least $k$ of the components are collision-resistant. One trivially gets a $(k,\ell)$-robust combiner by concatenating the output of any $\ell-k+1$ of the components, unfortunately this is not very practical as the length of the output of the combiner is quite large. We show that this is unavoidable as no black-box $(k,\ell)$-robust combiner whose output is significantly shorter than what can be achieved by concatenation exists. This answers a question of Boneh and Boyen (Crypto'06).
BibTeX
@misc{eprint-2006-21839,
  title={Non-Trivial Black-Box Combiners for Collision-Resistant Hash-Functions don't Exist},
  booktitle={IACR Eprint archive},
  keywords={foundations / hash functions, combiners},
  url={http://eprint.iacr.org/2006/348},
  note={ pietrzak@di.ens.fr 13437 received 16 Oct 2006},
  author={Krzysztof Pietrzak},
  year=2006
}