CryptoDB
Random Oracle Combiners: Merkle-Damgård Style
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| Abstract: | 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 h1 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λ, where λ 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_{h_1,h_2}^{Z_1,Z_2}(M ) = h_1^* (M, Z_1) ⊕ h_2^*(M, Z_2), where Z_1, 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 = λ + O(1). |
BibTeX
@inproceedings{eurocrypt-2025-35098,
title={Random Oracle Combiners: Merkle-Damgård Style},
publisher={Springer-Verlag},
author={Yevgeniy Dodis and Eli Goldin and Peter Hall},
year=2025
}