Cryptology ePrint Archive: Report 2013/210
Cryptophia's Short Combiner for Collision-Resistant Hash Functions
Abstract: A combiner for collision-resistant hash functions takes two functions as input and implements a hash function with the guarantee
that it is collision-resistant if one of the functions is. It has been shown that such a combiner
cannot have short output (Pietrzak, Crypto 2008); that is, its output length
is lower bounded by roughly $2n$ if the ingoing functions output $n$-bit hash values.
In this paper, we present two novel definitions for hash function
combiners that allow to bypass the lower bound: the first is an extended semi-black-box definition.
The second is a new game-based, fully black-box definition which allows to better analyze combiners in
idealized settings such as the random-oracle model or indifferentiability framework (Maurer, Renner, and Holenstein, TCC 2004). We then present a new combiner
which is robust for pseudorandom functions (in the traditional sense), which does not increase the output length of
its underlying functions and which is collision-resistant in the indifferentiability setting. Our combiner is particularly relevant in practical
scenarios, where security proofs are often given in idealized models, and our combiner, in the same idealized model,
yields strong security guarantees while remaining short.
Category / Keywords: foundations / hash functions, combiners, collision resistance, multi-property combiner
Original Publication (with major differences): 11th Conference on Applied Cryptography and Network Security (ACNS 2013)
Date: received 11 Apr 2013, last revised 26 Jun 2014
Contact author: arno mittelbach at cased de
Available format(s): PDF | BibTeX Citation
Version: 20140626:134437 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]