Thread by @SarahJamieLewis

This is cool, earlier this year I looked into the privacy of FMD (by @gabrie_beck et al) including simulations of attacks on realistic datasets.

Now, @Istvan_A_Seres et al have performed their own analysis and, in addition, have shown attack improvements on those same datasets.

https://twitter.com/Istvan_A_Seres/status/1437847195567411201

You can find my original dive into those datasets as part of the book I put together for fuzzytags (a rust implementation of FMD)

docs.openprivacy.ca/fuzzytags-book…

The attack improvements come from considering temporal relationships (the probability of receiving messages over a given threshold in a period of time) instead of just over the lifetime of the system.

This can be devastating if false positive rates are poorly selected.

One thing this new analysis does not consider is the existence of, what I call, "entangled tags" (see: docs.openprivacy.ca/fuzzytags-book…)

Basically FMD schemes permit anyone to efficiently forge tags that 100% match multiple users.

I recently release an update to fuzzytags that makes use of avx2 speedups in dalek ristretto to allow a consumer desktop to produce a completely entangled tag for 2 parties in ~79 seconds:

https://twitter.com/SarahJamieLewis/status/1395788016921108480

But, importantly, under the FMD threat model the routing server can only perform attacks given information about false positive rates well below 2^24 which means that you can partially entangle a tag to multiple parties that the server cannot distinguish.

And further you can do this both altruistically (to hide you are sending a message to someone by also entangling it to someone else), and maliciously (to implicate someone else in a deniable way).

I'm currently working on a project called Niwl which is best described as a mixnet design that makes heavy use of fuzzy message detection with entangled tags to improve both decentralization and auditability.

git.openprivacy.ca/openprivacy/ni…

Basically by adding mix nodes to an FMD scheme you can allow those nodes to take on the bandwidth-heavy and altruistic anonymity functions to provide for bandwidth-lite clients...

...those clients can, in addition, make use of entangling to check that mix nodes are acting honestly without adding additional traffic to the network (by tagging some messages to their contact AND themselves)

There are a couple of other neat tricks you can do as well, like entangle a tag to both a well known mix node AND a contact. Or entangle tag a message to two different mix nodes.

See the fuzzytags book for a write up on generic strategies: docs.openprivacy.ca/fuzzytags-book…

I'll add that all this comes with a very large hic sunt dracones warning - all of this is an experimental design that requires more analysis and testing.

git.openprivacy.ca/openprivacy/ni…