Splitting the output of a wide hash in lieu of multiple independent hashes

Question

Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of shorter output.

For instance, double hashing is often used as a technique to compute the k independent indexes required by a Bloom filter rather than using k independent hashes, but this is often optimized to use a single wide hash and splitting its output. E.g., Google's Guava Bloom filter operates in this way using 128-bit Murmur3.

Alas, I've not been able to find any literature that addresses when it may be safe to do this. I.e., what properties should the wide hash function have for this to be acceptable? Is meeting the bit independence criterion sufficient?

Answer 1

This is a heuristic. Any use of hash functions is a heuristic.

Here is a justification why it is a reasonable/plausible thing to do. Suppose our hash function is a uniform random function $h:\{0,1\}^m \to \{0,1\}^{2b}$. Define $h_0(x)$ to be the first half of $h(x)$ and $h_1(x)$ to be the second half of $h(x)$. Then $h_0,h_1$ are independent uniform random functions with signature $\{0,1\}^m \to \{0,1\}^b$. It follows that if our hash function is indistinguishable from a uniform random function, then using its output in this way will be indistinguishable from using two independent smaller hash functions.