70 lines
3.0 KiB
Markdown
70 lines
3.0 KiB
Markdown
# 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 to provide the service.
|
||
|
||
It would be awesome if we could get an untrusted server to do the work for us without compromising metadata-resistance!
|
||
|
||
**fuzzytags** is a probabilistic cryptographic structure to do just that! Specifically it provides the following
|
||
properties:
|
||
|
||
* Correctness: Valid tags constructed for a specific public key will always validate when tested using the detection key
|
||
* Fuzziness: Invalid tags will produce false positives with probability _p_ related to the security property (_γ_)
|
||
* Security: An adversarial server with access to the detection key is unable to distinguish false positives from true positives. (Detection Ambiguity)
|
||
|
||
## Security (hic sunt dracones)
|
||
|
||
This crate provides an experimental implementation of the `FMD2` scheme described in ["Fuzzy Message Detection"](https://eprint.iacr.org/2021/089). Using
|
||
Ristretto as the prime order group.
|
||
|
||
This code has not undergone any significant review.
|
||
|
||
Further, the properties provided by this system are highly dependent on selecting a **false positive rate** _p_ and
|
||
**scheme constant** _γ_ for your system. There is no one-size-fits-all approach.
|
||
|
||
If _p_ is too low, then the probability of false positives will be very high.
|
||
|
||
If _p_ is too high, then an adversarial server will be able to link messages to recipients with low probability.
|
||
|
||
Likewise a large _γ_ means higher bandwidth costs, but a small _γ_ reveals more of the secret keys to the server and
|
||
increases false positives.
|
||
|
||
## Usage
|
||
|
||
Generate a key pair:
|
||
|
||
let gamma = 3;
|
||
let key = FuzzyTagKeyPair::generate(gamma);
|
||
|
||
`key.public_key` can be given to parties who you want to be able to communicate with you over a specific anonymous
|
||
messaging service / privacy-preserving application.
|
||
|
||
`key.detection_key` can be given to untrusted _adversarial_ servers.
|
||
|
||
`gamma` is security property (_γ_) in the system. For a given gamma, a tag generated for a specific public key will
|
||
validate against a random public key with a maximum probability of 2^-gamma.
|
||
|
||
## Generating Tags
|
||
|
||
let tag = public_key.generate_tag();
|
||
|
||
This tag can be attached to a message in a metadata resistant system.
|
||
|
||
## Verifying Tags
|
||
|
||
First it is necessary to extract a detection key for a given false positive probability 0 <= 2^-n <= 2^-γ.
|
||
|
||
This extracted key can then be given to an adversarial server can test a given tag against a detection key e.g.:
|
||
|
||
let detection_key = key.extract(5);
|
||
if detection_key.test_tag(tag) {
|
||
// the message attached to this tag *might* be for the party associated with the detection key
|
||
} else {
|
||
// the message attached to this tag is definitely *not* for the party associated with the detection key.
|
||
}
|
||
|
||
|