60 lines
3.1 KiB
Markdown
60 lines
3.1 KiB
Markdown
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.
|
||
|