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

Suppose two parties have hash functions $h_1$ and $h_2$ respectively, but each only trusts the security of their own. We wish to build a hash combiner $C^{h_1, h_2}$ 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 $$\widetilde{C}_{\mathcal{Z}_1,\mathcal{Z}_2}^{h_1,h_2}(M) = h_1(M, \mathcal{Z}_1) \oplus h_2(M, \mathcal{Z}_2),$$ where $\mathcal{Z}_1, \mathcal{Z}_2$ 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 $h_1$ and $h_2$ 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 $h_1$ and $h_2$ 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.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2023
random oraclecombinerhash functioncollision resistancemerkle damgard
Contact author(s)
dodis @ cs nyu edu
niels @ microsoft com
eg3293 @ nyu edu
pf2184 @ nyu edu
krzysztof pietrzak @ ist ac at
2023-07-05: approved
2023-07-04: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Yevgeniy Dodis and Niels Ferguson and Eli Goldin and Peter Hall and Krzysztof Pietrzak},
      title = {Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1041},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.