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