Paper 2021/1180

The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees?

István András Seres, Balázs Pejó, and Péter Burcsi


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 three different angles. First, we analyze three privacy provisions offered by FMD: recipient unlinkability, relationship anonymity, and temporal detection ambiguity. Second, we perform a differential privacy analysis and coin a relaxed definition to capture the privacy guarantees FMD yields. Finally, we simulate FMD on real-world communication data. Our theoretical and empirical results assist FMD users in adequately selecting their false-positive detection rates for various applications with given privacy requirements.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Financial Cryptography and Data Security 2022
Fuzzy Message Detectionunlinkabilityanonymitydifferential privacygame theory
Contact author(s)
seresistvanandras @ gmail com
bupe @ inf elte hu
pejo @ crysys hu
2021-12-06: revised
2021-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {István András Seres and Balázs Pejó and Péter Burcsi},
      title = {The Effect of False Positives: Why Fuzzy Message Detection Leads to Fuzzy Privacy Guarantees?},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1180},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.