[Cryptography] Bloom filter question

[Peter Fairbrother]

On 04/08/2025 18:14, John Levine wrote:

> Incidentally, someone sent me references that led to this 1970 paper which did
> the same thing I proposed, make an MD5 hash and use chunks of it as the bit
> indices:

To answer your original question, I can't see anything wrong with using 
bit chunks of a longer hash function. They are, after all different 
hashes, and should be statistically independent if the hash is good - 
and even if it is a little bad, I don't think it matters much, it might 
make it a tad more prone to false positives but that's all.

But I do have some concerns about your threat model. Bloom filters are 
not designed for secrecy or concealment.

For instance, if you only have one item in the filter it is going to be 
pretty sparse, and easily recognisable as a single item. Do you need 
dummy items? A nonce? A secret to add pre-hash?

If so, then don't forget Schneier's law, or at least the first part of 
it (I have problems with the second part). It applies to protocols as 
well as algorithms.


Peter Fairbrother