Entangled Tags

It is possible to generate fuzzytags for a given $\gamma$ that are valid for 2 or more parties at the same time.

This is done through $\text{FlagEntangled}$ - a function that takes in a vector of tagging keys and runs the $\text{Flag}$ function, as documented in the original paper for each of them (with the same $randz$) until it finds a $z$ that will generate the same tag for every tagging key.

Here we briefly outline a number of properties of entangled tags. In the next section we will consider how to apply these strategies in real-world deployments.

Multiparty Broadcast

Alice wants to send a message to Bob and Carol. She constructs a single tag that will validate against detection keys generated by both of them.

When an adversarial server matches the tag against all the keys it knows about it will discover that the tag matches both Bob and Carol (in addition to some number of false positives depending on the false positive rates of all the other parties using the server).

To construct such a tag Alice runs $\text{FlagEntangled(}\{X_{\text{bob}},X_{\text{carol}}\}\text{)}$.

The adversarial server will match the tag to the detection keys of both Bob and Carol. The server has no way of determining if the match is a broadcast to both parties, a unique message to one of Bob or Carol or a false positive for both.

Deniable Sending

Alice wants to send a message to Carol, but is concerned that Carol may have a detection key with too low false positive rate. Alice knows of a set of parties (and their public keys) who also use the adversarial server to send privacy messages. Alice searches for a tag that will validate against detection keys generated not only by Carol but a randomly selected party e.g. Eve.

When an adversarial server matches the tag against all the keys it knows about it will discover that the tag matches both Carol and Eve (in addition to some number of false positives depending on the false positive rates of all the other parties using the server).

Even if the server was to isolate this specific message as originating from Alice, they would not be able to derive the recipient through any kind of differential attack (as all attacks would also implicate Eve).

To construct such a tag Alice runs $\text{FlagEntangled(}\{X_{\text{carol}},X_{\text{eve}}\}\text{)}$.

Alice could choose to entangle all of her messages to Carol in this way, fully implicating Eve in her message sending regardless of Eve's false positive rate. If Eve attempted to decrypt the message she would not be able to and might assume that the tag was an unlikely false positive - as such too many of these messages might cause Eve to be suspicious. However, Eve might be a well known service or bot integrated with the privacy preserving application - allowing Alice cover without worrying about triggering suspicion.

Alice could also choose to entangle each message with a different random party.

While this strategy is, by itself, vulnerable to intersection attacks; it increases the number of potential relationships any adversary needs to rule out in order to derive the resulting metadata from the communication.

When combined with a large number of parties downloading all messages (or even downloading with high false positive rates) this strategy has the effect of increasing the anonymity set of the entire system.

It is worth nothing at this point that strategies can be combined, and their effects compound. When given a tag and a set of matches an adversarial server cannot distinguish between a true and false positive, an entangled deniable send or a group broadcast - or a combination!

Forging False Positives

Alice wants to send a message to Carol, but also wants to implicate Eve to the server. However Alice doesn't have enough time or computing power to generate a tag that will fully match against Eve's full $\gamma$-length key.

Instead Alice forges an entangled tag by running $\text{FlagEntangled(}\{X_{\text{carol}},X_{\text{eve}}\}\text{)}$, however, instead of checking all parts of the key at line $11$ she instead only checks up to a value $l$ that she believes is greater than or equal to the false positive rate of Eves detection key.

To the server the tag would match both to the detection key of both Carol and Eve, but when fetched Eve would assume it was a false positive (a much more likely one than in our previous example).