Background

A bloom filter is a bitmap which lets you test if an item is a member of a set, in constant time and constant space. It tells you with 100% certainty if the item is NOT in the set, and it tells you with variable certainty if the item MIGHT be in the set. In other words, it answers yes/no if an item is in the set, but there's a chance of false positives, but no chance of false negatives.

The probability of a false positive is based on the number of items in the set, and the number of bits in the bitmap. Here (http://hur.st/bloomfilter) is a calculator, for example, which lets you say how many items are in the set, and what probability you want for false positives, and it tells you how many bits should be in the bitmap, and how many bits you should set each time you are adding an element into the filter (they call this 'number of hashes').

So you can imagine there are a lot of really interesting applications for bloom filters when you want a really fast, compact way of knowing if something is LIKELY to be true. Like, 'is this request in my cache?'

Bloom filters can also be used to provide some interesting privacy-preserving properties. In Bitcoin, for example, you have a wallet with money stored at a bunch of addresses, and unused addresses where new money can come in. You don't want anyone to just be able to look into your wallet and know all your addresses, but you DO want to be notified when someone sends you money. So you load up a bloom filter with a bunch of addresses which you expect any new payments will come in on, and you can share that bitmap with other people on the network. When new payments come in, the server can check them against the bitmap and forward you any matching transactions. In this case, you would setup a high probability of false positives, because you don't want even the servers to know which transactions are yours, but you don't want the server to just send you EVERYTHING.

Problem Statement

So we have a set 'S' which has been encoded in a bloom filter a.k.a. bitmap on the server. And we have a client with an element 'x' they want to check if it's a member of the set. But we don't want to disclose 'x' to the server, and we don't want to disclose the bitmap to the client. As the paper says, 'x' and BF(s) are kept secret from each other.

On the face of it, this seems really easy just by the very nature of how bloom filters work. Client would give the server a list of bits to check are TRUE in the bitmap, but do all the hashing to calculate that checklist on the client-side. This appears to keep 'x' secret from the server, but obviously it's trivial for the client to come up with a bunch of requests to ultimately discover the full state of the bitmap. Also, if 'x' IS in the set, the server could compare the checklist it received from the client, to the checklist of each element in the set, and discover 'x'.

Method

What the paper says is, instead of hashing each element to build the checklist, we will hash a blind signature of each element. A blind signature is a cryptographic signature of 'x' where the signing key (sk) can be kept secret from 'x'.

To construct the bloom filter on the server, instead of just hashing 'x', we will hash the signature of 'x'. Note, at this point it's not a 'blind' signature, since it's all happening on the server.

Then when a client wants to check 'x' against BF, the server can actually give the BF to the client, because in order for the client to USE the bloom filter, it needs to get its 'x' signed by the server! Now, we can use a blind-signature protocol between the client and the server, to basically "unlock" the BF for a specific 'x', without ever seeing 'x' on the server.

It's like server-based access control to a client-side bloom filter.

BTW - I wish a prerequisite for publishing these papers was an open-source sample implementation! :-)