Slashdot Mirror
LOAF - Distributed Social Networking Over Email
FamousLongAgo writes "LOAF (List Of All Friends) is an extension to email that lets you send out address book data without compromising your privacy. LOAF appends a hash-like data structure to each outgoing email, and collects similar attachments from the people who write to you. These files can be queried to see if they contain a given email address, but they can't be reverse-engineered to reveal the list of addresses used to construct them. LOAF lets you check whether someone emailing you for the first time is a complete stranger, or appears in the address books of some of your trusted correspondents. And as a decentralized application, LOAF offers an interesting alternative to current social networking sites like Orkut or Friendster."
They've included a nice analysis of the types of attacks including the Ex-Girlfriend attack, Marc Canter attack, and Dictionary Attacks in the writeup
The configurable false positive rate can make Bloom filters resistant to dictionary attack, but it also renders them less useful. Given a false positive rate of c, and a dictionary with k elements, a dictionary attack will result in ck false hits. This rate goes down if you can collect multiple filters from the same user that are either 1) of different length, or 2) use different hash functions (salts, in our implementation). False positives in either case will be different, so for n filters the false positive rate will drop to c^n.
This implies that the truly paranoid should use a presized filter large enough to contain as many correspondents as they ever expect to have on record, and an invariant set of salts. Under those conditions, collecting multiple filters will not change the false positive rate. A mostly empty large filter might have an unacceptably low false positive rate, so you would want to pad the list of real emails out with random data, to maintain a constant ratio of on/off bits as well.
The tradeoff with a high false positive rate is that the filter will be less useful to legitimate recipients. An intriguing possibility is that of sending out very inaccurate filters that are updated on a regular basis (for example weekly) so that a user has to accumulate a certain number of the filters in order to run queries with a good degree of certitude. This spreads private information over several filters and ensures that an eavesdropper who intercepts only one file will find it of very limited value.
And most importantly they say: Of course, the truly paranoid would be crazy to use LOAF.
An Indian-American Hindu committed to non-violent thought/speech/action alarmed by the global explosion of radical Islam
An (bad) example would be that the "encoding" function is the ascii values for the first and third character before the @ and the first character after the @ - those bits of a 128 bit Bloom filter are "lit up" for your address, so that means:
all map to the same bits being lit up in the bloom filter, there is no real way to "reverse engineer" it and since it does not assume no collisions (unlike MD5 and SHA*) it is not expected to have unique mappings - that's a feature, as they say.
There is no central list. The concept is that you append a list of YOUR friends to the end of each email you send. No one can read the list alone, but they can check if specific addresses are in it. So when someone new emails you, you check their address against all the known-good LOAF hashes youve recieved, this will tell you if they are a friend of a friend of yours.
Indeed, Bloom Filters are the shit.
;)
These days, in my spare time, I'm writing a p2p program -- think of it as a swarm-download system, like BitTorrent, on an overlay network topology, like eMule (only eMule uses Kademlia, and I'm using Pastry). It has been shown, here and here, that Bloom Filters can drastically reduce the traffic generated when searching peer to peer networks. I recently coded a Java implementation of a Bloom Filter for my p2p program, and it works great in testing. (But the p2p program isn't anywhere near done, so don't ask about it
Furthermore, Bloom Filters can be compressed -- see Michael Mitzenmacher's work here. The idea that you can compress a Bloom Filter is a little counter-intuitive, because the size of the bit vector and the number of hash functions are derived using calculus to maximize the compactness of the set, for a given false positive rate -- thus, in this state, it is non-compressable (it is "already compressed" by simply being an optimal Bloom Filter). To compress a bloom filter, you must choose a large bit vector, and a non-optimal number of hash functions, then apply the compression algorithm (typically arithmetic coding). Because the bit vector is so large, it is sparsely populated -- and so compression works.
Often you can save 10% and 20% on the size of your bloom filter, while having a lower false positive rate. Score!
A very nice, very interesting survey of all the applications of Bloom Filters can be found here.
- sm