metadata resistant message tagging for privacy preserving systems.
Go to file
Sarah Jamie Lewis 703f1736f5 update Cargo with new description and repo 2021-01-30 11:39:58 -08:00
benches Settle on a name 2021-01-30 11:33:30 -08:00
src Settle on a name 2021-01-30 11:33:30 -08:00
.gitignore More documentation 2021-01-29 18:24:27 -08:00
Cargo.toml update Cargo with new description and repo 2021-01-30 11:39:58 -08:00
LICENSE LICENSE 2021-01-30 11:38:01 -08:00 Update README 2021-01-30 11:36:48 -08:00
rustfmt.toml Formatting 2021-01-29 15:47:40 -08:00


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". 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.


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.