Statistical Attacks

Using some basic binomial probability we can use the false positive rate of reach receiver tag to calculate the probability of matching on at least X tags given the false positive rate. Using this we can find statistically unlikely matches e.g. a low-false positive key matching many tags in a given period.

This can be used to find receivers who likely received messages in a given period. This attack works regardless of how many parties are downloading everything, and is entirely dependent on the receiver choosing that is suboptimal for the number of messages they receive.

Deriving the Social Graph

If it is possible to group tags by sender then we can perform a slightly better attack and ultimately learn the underlying social graph with fairly low false positive rates (in simulations we can learn 5-10% of the underlying connections with between 5-12% false positive rates.)

The method is the same as above, but look at the probability that a party would have matched at least X tags from a specific sender given their false positive rate.

Notably, this latter attack reveals something important about choosing parameters for fuzzytags - p must be chosen to take into account not just total number of messages, but total number of messages from a given source (or it must be assumed that the server will never be able to isolate tags from a given sender)