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

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?

• Splitting one hash to two outputs is called "two-for-one hashing" in T D Ahle et al. The Power of Hashing with Mersenne Primes, though it seems like the term is only used in the paper so far. Feb 22, 2022 at 3:28
• @pcpthm thank you. I'll have to spend some time digesting the paper. Feb 23, 2022 at 22:27

1 Answer

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.

• Yes, that makes sense. But given that a hash is not a true uniform random function, what I am wondering is what statistical properties or tests must the output have or pass for this heuristic to be acceptable? I figured bit independence of the output, i.e., the lack of pairwise correlation between the output variables, would be a good proxy for assuming and treating two halves of the output as independent functions. I noticed it is one of the tests that smhasher performs. Feb 15, 2022 at 7:55
• @Dumbfounded, I don't think you're going to find a useful set of properties that is more helpful in practice. The way we design, pick, or use hash functions in practice is not by enumerating special properties we want them to have and then somehow verifying/proving/ensuring those properties definitely hold. So I don't think the direction you're heading is one that is ultimately going to be fruitful or helpful to you. "Randomness tests" are kind've a lie; they can tell you if a function is bad (in a certain sense), but not that the function is good.
– D.W.
Feb 15, 2022 at 7:58