Random Oracle Combiners: Merkle-Damgård Style
摘要
A Random Oracle Combiner (ROC), introduced by Dodis et al. (CRYPTO ’22), takes two hash functions \(h_1,h_2\) from m bits to n bits and outputs a new hash function C from \(m'\) to \(n'\) bits. This function C is guaranteed to be indifferentiable from a fresh random oracle as long as one of \(h_1\) and \(h_2\) (say, \(h_1\) ) is a random oracle, while the other \(h_2\) can “arbitrarily depend” on \(h_1\) . The work of Dodis et al. also built the first length-preserving ROC, where \(n'=n\) . Unfortunately, despite this feasibility result, this construction has several deficiencies. From the practical perspective, it could not be directly applied to existing Merkle-Damgård-based hash functions, such as SHA2 or SHA3. From the theoretical perspective, it required \(h_1\) and \(h_2\) to have input length \(m> 3\lambda \) , where \(\lambda \) is the security parameter. To overcome these limitations, Dodis et al. conjectured—and left as the main open question—that the following (salted) construction is a length-preserving ROC: \(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, and \(f^*\) denotes the Merkle-Damgård-extension of a given compression function f. As our main result, we resolve this conjecture in the affirmative. For practical use, this makes the resulting combiner applicable to existing, Merkle-Damgård-based hash functions. On the theory side, it shows the existence of ROCs only requiring optimal input length \(m=\lambda +O(1)\) .