In reply to @sarahjamielewis:matrix.org
A fun fuzzytags observation - it's actually trivial to construct a fuzzy tag such that it will pass the tests of multiple public keys simultaneously (and depending on gamma and how long you wanna wait to generate) pass a complete test too.

Which means for braodcast you could publish single messages and know that multiple parties would receive it, regardless of their false positive rate - only needing to know their public keys before hand.

In reply to @seresistvanandras:matrix.org
isn't this attack only possible by the server? in order to set the tag to your target false positive public keys, you would need to know their corresponding detection keys which is only known by the server. or what am I missing?

Hi!

Been a few months since I was heads deep in fuzzy message detection (I dumped a bunch of thoughts https://docs.openprivacy.ca/fuzzytags-book/introduction.html and in the code back then which might also prove helpful).

Senders always have access to the full public key and so can always construct a valid tag that will pass a test by any derived detection key. The multiple public key matching is done by filtering the generated randomness to find values that work for all of the public keys you want to match (this gets harder as the number of public keys increases and/or as gamma increases). i.e. keys generated with a public key will always match

The server has access to the derived detection keys, which are ostensibly much shorter (and so can simply brute force tags to match any arbitrary(?) subset of tags, but that is less interesting, since the server can obtain valid tags in other ways too, and injecting notifications is inherent to the underlying problem and not something that is server specific.

In reply to @seresistvanandras:matrix.org
If my understanding is correct then what you do is you observe the skew between the probability distributions of expected number of messages and the actual number of "received messages". One straightforward extension would be to this is to execute this function recursively. Like you remove from the graph the nodes which you deem to be deanonymized and then repeat the whole process on the remaining subgraph. Do you think this kinda trivial extension of this function would make sense or would improve your deanonymization attack?

I've played around with this attack a little, in the context of scenarios where no one downloads all messages. In those scenarios it is trivial to filter out the anonymity set over time. (for a set of 1000 users it can take as few as 3 messages given prior knowledge that those 3 messages are related)

The one complication is in accommodating parties that do download everything. They are the effective anonymity floor of the system and they can't be filtered out naively and do impact the usefulness of any derived social graph. So given any set of parties and a set of messages the cardinality of potential deanonymizations for each message will always be >= the cardinality of the set of parties who download everything.

In reply to @seresistvanandras:matrix.org
sorry if these are too trivial ideas and were already discussed either here on twitter. Sadly did not read everything on the topic. anyways would be quite interested to hear any idea/opinion for further deanonymizing fuzzy message detection :) If I'm not mistaken you only consider this skew for a way to deanonymise users...but is there any other heuristic to deanonymise users?

I documented a few general approaches here: https://docs.openprivacy.ca/fuzzytags-book/risk-model.html

They basically split into 2 domains: intersection attacks (like above) given prior knowledge of structure of communication and statistical attacks based on the expected false positive rate. Both are highly effective in simulations, but both are undermined in proportion to the set of parties who download everything.