3 ms·
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% certaint
by zaroth 13y ago
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 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! :-)
- jffry 13y agoI haven't read the paper (yet) but thanks for your thorough explanation. I need to go implement a bloom filter to help make them feel less like magic.
- saurik 13y ago> BTW - I wish a prerequisite for publishing these papers was an open-source sample implementation! :-) I sometimes feel the same, but much interesting work in algorithms has been done by people who are unable to program in an executable language.
- dllthomas 13y agoYes, but they usually have access to grad students...
- dllthomas 13y ago> 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. This wording is hard to understand - particularly the first clause. I assume you grok it, but for anyone confused: it returns either "no" or "maybe". If it returns no, you're 100% confident in that no. If it returns maybe it might be "yes" or "no" so you have to do a more thorough check in another kind of structure. The advantage being that you get that "no" or "maybe" super fast, so much of the time (any time you get a "no") you can stop looking early.
- zaroth 13y agoThanks, I also edited it a bit for clarity.