Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have been working on a Bloom Filter implementation recently and after a discussion with a co-worker about how many hashing functions to use I told him I was limited with using hashing functions that are already implemented and didn't want to risk the loss of distribution if I derive hashing functions from them.

We can assume that the distribution of any hashing function is not 100% perfect. It's very good for many, but not perfect. Is there any existing literature that describes the loss of distribution? I am not using the hashing functions for cryptographic purposes directly, because in a bloom filter it's only used as an index, and it's the distribution is the most important for my needs - but I assume they are related.

share|improve this question
    
Are you using cryptographic hash functions? If not, this is off-topic for Cryptography.SE. –  D.W. Dec 16 '13 at 1:52
    
    
@D.W. Yes I am using cryptographic hashing functions. SHA1, SHA256, and MD5. –  Kristopher Ives Dec 16 '13 at 3:47
1  
As far as non cryptographic uses are concerned, a cryptographic hash is a perfect. –  CodesInChaos Dec 16 '13 at 9:08
2  
For the purpose of a Boom Filter, as described in wikipedia, you can do HASH(element||"Function<N>"), with apropiate different N's, as it's done in BitCoin mining, to get virtually different hashing functions. –  daniel Dec 16 '13 at 10:42

1 Answer 1

For the purposes of a bloom filter you need a number of hash functions. Cryptographic hash functions are designed so that changing a single bit in the input should change many (around 1/2) of the output bits.

So, say you have a good hash function $h$ (e.g., SHA256 though MD5 should work for your purposes too) a good option for you would be to use use:

$h_1(m)=h("1" || m)$
$h_2(m)=h("2" || m)$
$\vdots$
$h_n(m)=h("n" || m)$

Where $||$ is concatenation. Then you only need one hash function. This is basically what they are doing in this java implementation.

Is there any existing literature that describes the loss of distribution?

Not that I am aware of. But think about it this way, if there were a significant change from the uniform distribution computable in a reasonable amount of time we wouldn't use the hash function for cryptographic purposes.

Now, is there some sort of attack you are worried about?

share|improve this answer
    
Not a specific attack but I am curious if anyone has done the math. My "gut" tells me that it's a compound of some kind, and we can assume that a good hashing algo might be 0.99 "distributed" but I am concerned with compounding like 0.99 * 0.99 * 0.99 ... –  Kristopher Ives Jan 3 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.