Paper 2023/1041
Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance
Yevgeniy Dodis, New York University
Niels Ferguson, Microsoft (United States)
Eli Goldin, New York University
Peter Hall, New York University
Krzysztof Pietrzak, Institute of Science and Technology Austria
Abstract
Suppose two parties have hash functions and respectively, but each only trusts the security of their own. We wish to build a hash combiner which is secure so long as either one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO'06; Pietrzak, Eurocrypt'07; Pietrzak, CRYPTO'08) showed no (noticeably) shorter combiner for collision resistance is possible.
We revisit this pessimistic state of affairs, motivated by the observation that collision-resistance is insufficient for many applications of cryptographic hash functions anyway. We argue the right formulation of the "hash combiner" is what we call random oracle (RO) combiners.
Indeed, we circumvent the previous lower bounds for collision resistance by constructing a simple length-preserving RO combiner
where are random salts of appropriate length. We show that this extra randomness is necessary for RO combiners, and indeed our construction is somewhat tight with this lower bound.
On the negative side, we show that one cannot generically apply the composition theorem to further replace "monolithic" hashes and by some simpler indifferentiable construction (such as the Merkle-Damgård transformation) from smaller components, such as fixed-length compression functions. Despite this issue, we directly prove collision resistance of the Merkle-Damgård variant of our combiner, where and are replaced by iterative Merkle-Damgård hashes applied to fixed-length compression functions. Thus, we can still subvert the concatenation barrier for collision-resistance combiners using practically small components.