Paper 2023/1041
Random Oracle Combiners: Breaking the Concatenation Barrier for CollisionResistance
Abstract
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 wellstudied 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 collisionresistance 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 lengthpreserving 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 MerkleDamgård transformation) from smaller components, such as fixedlength compression functions. Despite this issue, we directly prove collision resistance of the MerkleDamgård variant of our combiner, where $h_1$ and $h_2$ are replaced by iterative MerkleDamgård hashes applied to fixedlength compression functions. Thus, we can still subvert the concatenation barrier for collisionresistance combiners using practically small components.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A minor revision of an IACR publication in CRYPTO 2023
 Keywords
 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  History
 20230705: approved
 20230704: received
 See all versions
 Short URL
 https://ia.cr/2023/1041
 License

CC BYSA
BibTeX
@misc{cryptoeprint:2023/1041, author = {Yevgeniy Dodis and Niels Ferguson and Eli Goldin and Peter Hall and Krzysztof Pietrzak}, title = {Random Oracle Combiners: Breaking the Concatenation Barrier for CollisionResistance}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1041}, year = {2023}, url = {https://eprint.iacr.org/2023/1041} }