Robust Multi-property Combiners for Hash Functions Revisited

A robust multi-property combiner for a set of security properties merges two hash functions such that the resulting function satisfies each of the properties which at least one of the two starting functions has. Fischlin and Lehmann (TCC 2008) recently constructed a combiner which simultaneously preserves collision-resistance, target collision-resistance, message authentication, pseudorandomness and indifferentiability from a random oracle (

IRO

). Their combiner produces outputs of 5

n

bits, where

n

denotes the output length of the underlying hash functions.

In this paper we propose improved combiners with shorter outputs. By sacrificing the indifferentiability from random oracles we obtain a combiner which preserves all of the other aforementioned properties but with output length 2

n

only. This matches a lower bound for black-box combiners for collision-resistance as the only property, showing that the other properties can be achieved without penalizing the length of the hash values. We then propose a combiner which also preserves the

IRO

property, slightly increasing the output length to 2

n

 + 

ω

(log

n

). Finally, we show that a twist on our combiners also makes them robust for one-wayness (but at the price of a fixed input length).