Bloom filters are a nice data structure, and you should absolutely have them in your toolbox, but if you go looking for a reason to use one you are likely to wind up making things worse. The following is not valid reasoning: "Bloom filters are efficient. Therefore if I can find a way to use a bloom filter, my solution will be efficient."<p>The "SSH keys" protocol in the article seems like an example of this. It doesn't make any sense. Why would the server send the client a Bloom filter if the client has already told it what key it wants to check? The server only has to send one bit back to the client! And if the goal is to not trust the server with the client's (public) key, this protocol doesn't accomplish that either.<p>And if you do for some reason have to transmit the entire database of compromised SSH keys in a way that permits only membership tests, a Bloom filter isn't the most compact way to do it! For example, off the top of my head, you could calculate an (15+N)-bit hash for each element of the list, sort the hashes, and rice code the deltas. That would take very roughly 32768 * (N+2) bits and give about 1 in 2^N false positives. So for N=13 it is about the size of the bloom filter in the article but gives a false positive rate 8 times lower. This data structure isn't random access like a Bloom filter, but that doesn't matter for something you are sending over the network (which is always O(N)).