The concatenation combiner which simply concatenates the outputs of all hash functions is an example of a robust combiner for collision resistance. However, its output length is, naturally, significantly longer than each individual hash-function output, while the security bounds are not necessarily stronger than that of the strongest input hash-function. In 2006 Boneh and Boyen asked whether a robust black-box combiner for collision resistance can exist that has an output length which is significantly less than that of the concatenation combiner \cite{C:BonBoy06}. Regrettably, this question has since been answered in the negative for fully black-box constructions (where hash function and adversary access is being treated as black-box), that is, combiners (in this setting) for collision resistance roughly need at least the length of the concatenation combiner to be robust \cite{C:BonBoy06,C:CRSTVW07,EC:Pietrzak07,C:Pietrzak08}.
In this paper we examine weaker notions of collision resistance, namely: \emph{second pre-image resistance} and \emph{target collision resistance} \cite{FSE:RogShr04} and \emph{pre-image resistance}. As a generic brute-force attack against any of these would take roughly $2^n$ queries to an $n$-bit hash function, in contrast to only $2^{n/2}$ queries it would take to break collision resistance (due to the birthday bound), this might indicate that combiners for weaker notions of collision resistance can exist which have a significantly shorter output than the concatenation combiner (which is, naturally, also robust for these properties). Regrettably, this is not the case.
Category / Keywords: foundations / hash functions, combiners Publication Info: An extended abstract of this work appears in "8th Conference on Security and Cryptography for Networks (SCN 2012)" Date: received 21 Jun 2012 Contact author: arno mittelbach at cased de Available format(s): PDF | BibTeX Citation Version: 20120622:200328 (All versions of this report) Short URL: ia.cr/2012/354