Multi-server Fuzzy Message Detection

Christopher Goes; Yulia Khalniyazova; Enrique Larraia; Xuyang Song

Paper 2025/2072

Multi-server Fuzzy Message Detection

Christopher Goes, Heliax

Yulia Khalniyazova, Heliax

Enrique Larraia

, Heliax

Xuyang Song, Heliax

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.

Note: Updated email

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Fuzzy Message Detection
Contact author(s): cwgoes @ heliax dev
yulia @ heliax dev
elarraia @ gmail com
xuyang @ heliax dev
History: 2025-11-13: last of 2 revisions; 2025-11-10: received; See all versions
Short URL: https://ia.cr/2025/2072
License: CC BY

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}
}