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

Krzysztof Pietrzak

Paper 2006/348

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

Krzysztof Pietrzak

Abstract

A $(k, ℓ)$ -robust combiner for collision-resistant hash-functions is a construction which from $ℓ$ 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, ℓ)$ -robust combiner by concatenating the output of any $ℓ - 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 -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).

Metadata

Available format(s): PDF PS
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: hash functions combiners
Contact author(s): pietrzak @ di ens fr
History: 2006-10-20: received
Short URL: https://ia.cr/2006/348
License: CC BY

BibTeX

@misc{cryptoeprint:2006/348,
      author = {Krzysztof Pietrzak},
      title = {Non-Trivial Black-Box Combiners for Collision-Resistant Hash-Functions don't Exist},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/348},
      year = {2006},
      url = {https://eprint.iacr.org/2006/348}
}