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

Krzysztof Pietrzak

##### 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).

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
hash functionscombiners
Contact author(s)
pietrzak @ di ens fr
History
Short URL
https://ia.cr/2006/348

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},
note = {\url{https://eprint.iacr.org/2006/348}},
url = {https://eprint.iacr.org/2006/348}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.