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)

Formally

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 $\gamma$ secret keys $\vec{x}$ and a public key $\vec{X}=\{x_i\mathbf{G}:\forall x_i\in \vec{x}\}$

A fuzzytag consists of:

• a ciphertext, $\vec{c}$, of length $\gamma$,
• a group element: $\mathbf{U}=r\mathbf{G}$, where $r$ is a random scalar.
• and, a scalar: $y=r^{-1}\times (z-m)$ where $z$ is another random scalar, and $m$ is a scalar derived from the output of a hash function over $u$ and the $\vec{c}$.

The ciphertext is obtained by constructing a key $\vec{k}=\{k_i=H(\mathbf{U}||r{\mathbf{X}}_{\mathbf{i}}||w)\forall i\in \vec{X})\}$ and calculating $\vec{c}=\vec{k}\oplus \vec{1}$

Checking a text is done over a detection key $d$ of length $n$ where $\vec{d}={\vec{x}}_{0\dots n}$, this detection key can be given to an adversarial server to perform filtering.

$\vec{k}$ is recalculated by first deriving $w$ using $u$ and $y$ and then calculating $\{k_i=H(\mathbf{U}||x_i\mathbf{U}||w)\forall i\in \vec{x})\}$ and the plaintext is recovered $\vec{p}=\vec{k}\oplus \vec{c}$ and compared to $\vec{1}$.

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 $\mathbf{U}$ is not the identity element.
  • We assert that $y\ne 0$
• Reject tags intended for different setups:
  • We include $\gamma$ in the input to both the $H$ and $G$ hash functions.