Intersection Attacks

One of the most basic attacks primitives for any kind of false positive based scheme is an intersection attack, where the set of peers that match one tag is intersected against another set of peets that matches a different tag.

Any kind of intersection attacks break this scheme, even for a small number of messages i.e. if you learn (through any means) that a specific set of messages are all likely for a single party, you can diff them against all other parties keys and very quickly isolate the intended recipient - in simulations of 100-1000 parties it can take as little as 3 messages - even with everyone selecting fairly high false positive rates.

The corollary of the above being that in intersection attacks your anonymity set is the number of users who download all messages. This has the interesting side effect: the more parties who download everything, the more the system can safely tolerate parties with small false-positive rates.