fuzzymetatag/README.md

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