Paper 2021/089

Fuzzy Message Detection

Gabrielle Beck, Julia Len, Ian Miers, and Matthew Green


Many privacy-preserving protocols employ a primitive that allows a sender to "flag" a message to a recipient's public key, such that only the recipient (who possesses the corresponding secret key) can detect that the message is intended for their use. Examples of such protocols include anonymous messaging, privacy-preserving payments, and anonymous tracing. A limitation of the existing techniques is that recipients cannot easily outsource the detection of messages to a remote server, without revealing to the server the exact set of matching messages. In this work we propose a new class of cryptographic primitives called fuzzy message detection schemes. These schemes allow a recipient to derive a specialized message detection key that can identify correct messages, while also incorrectly identifying non-matching messages with a specific and chosen false positive rate $p$. This allows recipients to outsource detection work to an untrustworthy server, without revealing precisely which messages belong to the receiver. We show how to construct these schemes under a variety of assumptions; describe several applications of the new technique; and show that our schemes are efficient enough to use in real applications.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.ACM CCS
Contact author(s)
matthewdgreen @ gmail com
becgabri @ cs jhu edu
2021-11-22: last of 4 revisions
2021-01-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Gabrielle Beck and Julia Len and Ian Miers and Matthew Green},
      title = {Fuzzy Message Detection},
      howpublished = {Cryptology ePrint Archive, Paper 2021/089},
      year = {2021},
      doi = {10.1145/3460120.3484545},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.