Fuzzy Message Detection (FMD) is a recent cryptographic primitive invented by
Beck et al. (CCS’21) where an untrusted server performs coarse message
filtering for its clients in a recipient-anonymous way. In FMD – besides the
true positive messages – the clients download from the server their cover
messages determined by their false-positive detection rates. What is more,
within FMD, the server cannot distinguish between genuine and cover traffic. In
this paper, we formally analyze the privacy guarantees of FMD from four
different angles. First, we evaluate what privacy provisions are offered by
FMD. We found that FMD does not provide relationship anonymity without
additional cryptographic techniques protecting the senders’ identities.
Moreover, FMD only provides a reasonable degree of recipient unlinkability when
users apply considerable false-positive rates, and concurrently there is
significant traffic. Second, we perform a differential privacy (DP) analysis
and coin a relaxed DP definition to capture the privacy guarantees FMD yields.
Third, we study FMD through a game-theoretic lens and argue why FMD is not
sustainable without altruistic users. Finally, we simulate FMD on real-world
communication data. Our theoretical and empirical results assist FMD users to
adequately select their false-positive detection rates for various applications
with given privacy requirements.

By admin