Multi-server Fuzzy Message Detection

Christopher Goes; Yulia Khalniyazova; Enrique Larraia; Xuyang Song

Paper 2025/2072 Original: eprint.iacr.org/2025/2072 ↗

Multi-server Fuzzy Message Detection

Christopher Goes

Yulia Khalniyazova

Enrique Larraia

Xuyang Song

Abstract

Fuzzy Message Detection, or FMD, outsources detection of messages to an untrusted server, Beck et. al. CCS 2021. In this paper, we extend FMD to the multi-key setting: several servers are given different detection keys, all extracted from a single secret key. Multi-key FMD allows to combine tests from multiple servers locally by each receiver. This allows to set high false-positive rates on the servers, while attaining low rates on the receiver side. Striking this way a better balance between privacy and efficiency. We further formalize the notion of stealth public keys in the FMD setting. Last, we provide two constructions, one with short public keys.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
History: 2025-11-13: last updated; 2025-11-10: published
Short URL: https://ia.cr/2025/2072
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2025/2072,
      author = {Christopher Goes and Yulia Khalniyazova and Enrique Larraia and Xuyang Song},
      title = {Multi-server Fuzzy Message Detection},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2072},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2072}
}