Paper 2012/354

Hash Combiners for Second Pre-Image Resistance, Target Collision Resistance and Pre-Image Resistance have Long Output

Arno Mittelbach

Abstract

A $(k,l)$ hash-function combiner for property $P$ is a construction that, given access to $l$ hash functions, yields a single cryptographic hash function which has property $P$ as long as at least $k$ out of the $l$ hash functions have that property. Hash function combiners are used to hedge against the failure of one or more of the individual components. One example of the application of hash function combiners are the previous versions of the TLS and SSL protocols \cite{RFC:6101,RFC:5246}. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. An extended abstract of this work appears in "8th Conference on Security and Cryptography for Networks (SCN 2012)"
Keywords
hash functionscombiners
Contact author(s)
arno mittelbach @ cased de
History
2012-06-22: received
Short URL
https://ia.cr/2012/354
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/354,
      author = {Arno Mittelbach},
      title = {Hash Combiners for Second Pre-Image Resistance, Target Collision Resistance and Pre-Image Resistance have Long Output},
      howpublished = {Cryptology ePrint Archive, Paper 2012/354},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/354}},
      url = {https://eprint.iacr.org/2012/354}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.