Paper 2026/1950

Sprinkle the Salt: RO-combiners with $\mathcal{O}(n)$ random bits

Abstract

At Crypto 2023, Dodis, Ferguson, Goldin, Hall, and Pietrzak [DFGHP23] introduced and constructed Random Oracle (RO) combiners, rejuvenating the well-studied area of cryptographic combiners. RO-combiners are (salted) hash function modes of operation over multiple underlying compression functions that achieve indifferentiability as long as at least one of the underlying compression functions is ideal. Unfortunately, the security of RO-combiners turns out to be a multi-stage game, and the well-established indifferentiability results for hash function modes cannot be lifted to RO-combiners via the composition theorem. There have been two works aiming to construct RO-combiners from scratch. [DFGHP23] built an indifferentiable compression-function combiner, whose deployment requires a new hash implementation, limiting its scope. The follow-up work by Dodis, Goldin, and Hall [DGH25] at Eurocrypt 2025 constructed the first secure RO-combiner capable of handling a large but fixed-length message using \MD hashing. However, implementing their construction either requires a random salt larger than the message length (potentially exponential in the security parameter) or incurs up to an exponential number of calls to the underlying \MD hash. In this paper, we introduce a new design principle for robust RO-combiners that yields efficient and instantly deployable solutions. At the same time, the principle is generic, enabling the construction of robust variable-input-length RO-combiners from a wide class of popular hashing modes. Our main result constructs robust RO-combiners from standard \emph{preimage-aware} hash constructions by salting each compression function call and applying a post-processor. The required salt size is $\mathcal{O}(n)$ for $n/2$-bit security and is independent of the input message size. Moreover, the combiner makes only a single call to each of the underlying hash modes. We show instantiations using both linear \MD and tree hashing. From an instantiation perspective, with only a simple modification to message padding, our variable-length \MD combiner can be readily obtained with SHA-256 or Blake2. The combiner requires just $1408$ bits of randomness while achieving $128$-bit security and a message processing rate of $320$ bits per compression-function call.