I’m collecting here some insights from this paper. They may be helpful to design the solution (see countermeasures below).
Recipient unlinkability captures the (in)ability to relate resources consumable by the same user. The adversary is allowed to observe the network, i.e. traffic involving the servers and the private state pool \mathsf{BB}_0. A specific attack vector inspects the anonymity sets of any two shielded resources to infer whether they are consumable by the same user. In the paper, the authors show that the adversary success is lower bounded by (a negligible function in) the number of users whenever the false-positive rate is the same for all users. The smaller these are, the easier to break recipient unlinkability.
Relationship anonymity says that it is not possible to determine the creator and the consumer of a resource. If for any reason the creator and the number of resources it created are known to the servers holding the detection keys, the relationship can be inferred by looking at how many flag ciphertexts a consumer downloads from a given creator.
Temporal detection ambiguity The servers should not be able to tell whether they found a true or a false positive match in a given time interval. In our case, in a given slot of locations of \mathsf{BB}_0. It seems that if the false positive rate is small, then temporal detection is possible. Indeed, one can deduce the probability distribution of false positives (according to the paper, it is a binomial distribtuion). If the actual number of consumable resources for the user is large, then the distribution over false positives can be approximated with a normal distribution. One can now look at the number of downloaded ciphertexts (or passed to the decryption layer), to see if they are statistically close or far to the approximated normal distribution. This tells whether or not in that time interval the downloaded resources contain consumable resources by the user or not.
Countermeasures that we could implement
Split user anonymity set view. A countermeasure for the recipient unlinkability attack is to split the anonymity set view. Since each server holds only a partial view, to launch the attack all servers that jointly hold the view should be compromised. For example, to split the view in the stacked filtering approach, we can have a layered arrangement: servers in the i-th layer split their output and send it to different nodes at the i+1 layer. (This protects against the servers themselves, encrypted communication protects the anonymity set against eavesdroppers.)
Note: I think this may also protect against other traffic inspection attacks. Again, in the stacked filtering toplogy, a server has a single decryption key, but with a straight-line arrangement, it is effectively given a set of filtered ciphertexts at lower false-positive rates.
Flag ciphertexts in the shielded private pool. Attacking relationship anonymity should not be an issue as long as the resource creator remains anonymous. Thus, as long as either of the following holds:
- the flag ciphertexts f_m are in the public shielded state pool \mathsf{BB}_0. This assumes that it is hard to tell apart resources’s creators by looking at \mathsf{BB}_0.
- the sender communicates anonymously to the servers their flag ciphertexts f_m.
Append dummy traffic. To avoid temporal detection ambiguity, servers could append dummy data to their filtered/decrypted ciphertexts. This would have the effect of downloading as with large false positive rates. Communication bandwidth degrades, but users do not need to trial-decrypt to discard the dummy data.