3 ms·

I'll put an example in techie-English: Say the government has a giant No-Bus-list of suspected naughty people that shouldn't be allowed to ride busses. The co

by nullc 13y ago

I'll put an example in techie-English: Say the government has a giant No-Bus-list of suspected naughty people that shouldn't be allowed to ride busses. The complete list is highly secret, because we wouldn't want people improperly listed challenging it in court. Ahem I mean we wouldn't want terrorists to change their strategy to evade. A Bus operator needs to query passengers against the list, but doesn't want to tell the government the names of all their passengers (Because they know the government will leak the data to their competition. What? You thought they cared about privacy? Give me a break). So what the government does is computes a digital signature for each national ID number in the naughty list using a private key known only to the government and puts the digital signature instead of the name in a bloom filter. They send the whole bloom filter to the Bus operator. (The bloom filter is much smaller than the list— which is good because the list is gigantic) The bus operator learns nothing about the list except an approximate upper bound on its size. Then when a passenger shows up the bus operator encrypts the passengers ID number and sends it to the government— imagine the encryption as a sealed envelope. The government can't read it because it's encrypted. The government performs a blind signing operation— sort of like signing a piece of carbon paper inside an envelope without opening it (this requires the encryption and signing methods be a kind that allows for this) and sends back the blind-signed passenger name. The Bus operator decrypts to obtain the signature and checks it against the bloomfilter. If they get a hit on the filter they redirect the passenger to Guantanamo for enhanced interrogation. (A bloom filter, of course, has no false negatives: exactly the property we need to keep America safe from Terrorism)

pudquick 13y ago
Thank you for the write up here. I was going to post something similar, but instead use the example of a lawyer wanting to perform name searches on the list of people the NSA has information on. One point I do want to make, though, for anyone that can't tell the last paragraph might be a bit of a joke: while a Bloom filter never has false negatives, it will always have a certain amount (controllable by adjusting the size of the filter) of false POSITIVES. Think of it this way: a Bloom filter lets you determine with 100% accuracy if someone is a member of Group A (the set you build the filter with) but less than 100% accuracy if they're instead only a member of Group Not-A. In the example above, if Group A is the Evil Terrorists (which you build the Bloom filter with), then there's a non-zero chance that a Good American member of Group Not-A may end up falsely identified as a terrorist. If Group A is instead made up of every Good American, you flip the problem and now have the non-zero possibility of falsely identifying a Evil Terrorist (from group Not-A) as a benign Good American. If you attempt to use them to solve a problem like this, you have to have a mechanism in place to deal with the very real case of a false positive (or decide which group to build the filter with - which one is less damaging to have show up as a false positive). Bloom filters are cool, but they're a tradeoff of speed and memory for accuracy. They are not a perfect index if you're trying to determine A vs. Not-A-ness. The best concept is a cache lookup - if it's not a member of the Bloom filter, you DEINITELY don't have it cached, but if there's a hit then you very very very likely have it cached (and if you don't, then at least you're only redirecting a vanishingly small number of false positives back to the live server). Google actually uses this for determining attack sites in Chrome without giving out an index of all the attack sites they know of. They give out a Bloom filter instead with the web client. When you visit a site, if it's a miss on the Bloom filter, it is currently not known by Google to be an attack site. However, if you get a hit, it first calls home to a Google server to re-verify that the site is not a false positive and confirm it is indeed an attack site. In this way, since the vast majority of the web is not malicious, they only impose a bandwidth cost when they think you may have stumbled upon a bad site (member of the Bloom filter) - but they get a chance to weed out the false positives before telling you.
- dllthomas 13y ago
  > Think of it this way: a Bloom filter lets you determine with 100% accuracy if someone is a member of Group A (the set you build the filter with) but less than 100% accuracy if they're instead only a member of Group Not-A. ... narrowing the scope to the lookup itself. Obviously, for actual people and actual groups things are messier (assuming a 100% chance the terrorist gave you one of their known aliases seems inappropriate).
- nullc 13y ago
  Indeed, I wondered if the dark humor of the last comment might be a little too subtle. :) One of the bummers about this scheme is that it doesn't have the property of making the bandwidth for all queries constant (get the bloom filter) instead of linear in the number of lookups that the regular non-private use of bloom filters has. But thats the tradeoff for the bi-directional privacy. I could actually imagine a production system using this, which is something I can't say for most privacy preserving query techniques.
- hrjet 13y ago
  > If you attempt to use them to solve a problem like this, you have to have a mechanism in place to deal with the very real case of a false positive (or decide which group to build the filter with - which one is less damaging to have show up as a false positive). Hmm, so it is possible to have two bloom filters? One for the black list and one for the white list. If black list filter says no, then the element is definitely in white list. And vice-versa.

by nullc 13y ago

pudquick 13y ago

Thank you for the write up here. I was going to post something similar, but instead use the example of a lawyer wanting to perform name searches on the list of people the NSA has information on. One point I do want to make, though, for anyone that can't tell the last paragraph might be a bit of a joke: while a Bloom filter never has false negatives, it will always have a certain amount (controllable by adjusting the size of the filter) of false POSITIVES. Think of it this way: a Bloom filter lets you determine with 100% accuracy if someone is a member of Group A (the set you build the filter with) but less than 100% accuracy if they're instead only a member of Group Not-A. In the example above, if Group A is the Evil Terrorists (which you build the Bloom filter with), then there's a non-zero chance that a Good American member of Group Not-A may end up falsely identified as a terrorist. If Group A is instead made up of every Good American, you flip the problem and now have the non-zero possibility of falsely identifying a Evil Terrorist (from group Not-A) as a benign Good American. If you attempt to use them to solve a problem like this, you have to have a mechanism in place to deal with the very real case of a false positive (or decide which group to build the filter with - which one is less damaging to have show up as a false positive). Bloom filters are cool, but they're a tradeoff of speed and memory for accuracy. They are not a perfect index if you're trying to determine A vs. Not-A-ness. The best concept is a cache lookup - if it's not a member of the Bloom filter, you DEINITELY don't have it cached, but if there's a hit then you very very very likely have it cached (and if you don't, then at least you're only redirecting a vanishingly small number of false positives back to the live server). Google actually uses this for determining attack sites in Chrome without giving out an index of all the attack sites they know of. They give out a Bloom filter instead with the web client. When you visit a site, if it's a miss on the Bloom filter, it is currently not known by Google to be an attack site. However, if you get a hit, it first calls home to a Google server to re-verify that the site is not a false positive and confirm it is indeed an attack site. In this way, since the vast majority of the web is not malicious, they only impose a bandwidth cost when they think you may have stumbled upon a bad site (member of the Bloom filter) - but they get a chance to weed out the false positives before telling you.

dllthomas 13y ago
> Think of it this way: a Bloom filter lets you determine with 100% accuracy if someone is a member of Group A (the set you build the filter with) but less than 100% accuracy if they're instead only a member of Group Not-A. ... narrowing the scope to the lookup itself. Obviously, for actual people and actual groups things are messier (assuming a 100% chance the terrorist gave you one of their known aliases seems inappropriate).
nullc 13y ago
Indeed, I wondered if the dark humor of the last comment might be a little too subtle. :) One of the bummers about this scheme is that it doesn't have the property of making the bandwidth for all queries constant (get the bloom filter) instead of linear in the number of lookups that the regular non-private use of bloom filters has. But thats the tradeoff for the bi-directional privacy. I could actually imagine a production system using this, which is something I can't say for most privacy preserving query techniques.
hrjet 13y ago
> If you attempt to use them to solve a problem like this, you have to have a mechanism in place to deal with the very real case of a false positive (or decide which group to build the filter with - which one is less damaging to have show up as a false positive). Hmm, so it is possible to have two bloom filters? One for the black list and one for the white list. If black list filter says no, then the element is definitely in white list. And vice-versa.