In this short book we, Open Privacy, will document our investigations into [Fuzzy Message Detection](https://eprint.iacr.org/2021/089),
including extensions to the proposed scheme and simulation results when modelling realistic deployments.


![](./FuzzyTags_Logo.png)

# 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](https://eprint.iacr.org/2021/089) 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_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 \ldots 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 \neq 0$
* Reject tags intended for different setups:
    * We include $\gamma$ in the input to both the $H$ and $G$ hash functions.