In this short book we, Open Privacy, will document our investigations into Fuzzy Message Detection, including extensions to the proposed scheme and simulation results when modelling realistic deployments.

Introduction to Fuzzytags

Anonymous messaging systems (and other privacy-preserving applications) often require a mechanism for one party to learn that another party has messaged them.

Many schemes rely on a bandwidth-intensive "download everything and attempt-decryption" approach. Others rely on a trusted 3rd party, or non-collusion assumptions, to provide a "private" service.

It would be awesome if we could get an untrusted, adversarial server to do the work for us without compromising metadata-resistance!

fuzzytags is an experimental probabilistic cryptographic tagging structure to do just that!

Specifically fuzzytags provides the following properties:

  • Correctness: Valid tags constructed for a specific public key will always validate when tested using a derived detection key.
  • Fuzziness: Tags will produce false positives with probability p related to the security property (γ) when tested against detection keys they were not intended for.
  • Security: An adversarial server with access to the detection key is unable to distinguish false positives from true positives. (Detection Ambiguity)


For an in depth analysis see the origin paper Fuzzy Message Detection by Gabrielle Beck and Julia Len and Ian Miers and Matthew Green.

Note, that paper uses multiplicative notation, throughout this book we will use additive notation.

All parties in the fuzzy tag system derive an ordered set of secret keys and a public key

A fuzzytag consists of:

  • a ciphertext, , of length ,
  • a group element: , where is a random scalar.
  • and, a scalar: where is another random scalar, and is a scalar derived from the output of a hash function over and the .

The ciphertext is obtained by constructing a key and calculating

Checking a text is done over a detection key of length where , this detection key can be given to an adversarial server to perform filtering.

is recalculated by first deriving using and and then calculating and the plaintext is recovered and compared to .

Additional Checks

We perform the following additional checks when verifying a tag:

  • Discard tags that would validate for every single public key.
    • We assert that is not the identity element.
    • We assert that
  • Reject tags intended for different setups:
    • We include in the input to both the and hash functions.