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)

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.

More Detailed System Description

There exists a metadata resistant application that uses untrusted servers to mediate communication between parties.

Each party can be identified with a set of cryptographic identifiers and there exists methods in or external to the system to distribute keys securely and authentically.

Now, instead of each party adopting a download-everything approach to metadata privacy (or invoking non-collusion or other assumptions) we can leverage fuzzytags to reduce the number of messages downloaded from the server by each party while maintaining a formalized concept of metadata privacy.

Every party generates a FuzzyTagKeyPair, consisting of a FuzzyTagSecretKey and a FuzzyTagPublicKey. These keys will be generated with a parameter γ that relates to the minimum false-positive probability 2^-γ.

When submitting messages to the server for an intended recipient, the sender will generate a new tag from the recipients FuzzyTagPublicKey.

All parties will extract a FuzzyTagDetectionKey from their key pair. This key will be of length n and provide a false positive detection probability of 0 <= 2^-n <= 2^-γ. This detection key can be given to an adversarial server.

When fetching new messages from the adversarial server, the server first runs a test of the tag of the message against the parties' detection key. If the tag passes the test, the message (along with the tag) is provided to the recipient.

Finally, the recipient runs their own test of the tag against an extracted detection key such that FuzzyTagSecretKey == FuzzyTagDetectionKey i.e. the probability of a false positive will be 2^-n == 2^-γ. This will produce a subset of messages likely intended for the recipient, with a smaller probability of false positives.

Alternatively the recipient can simply try and decrypt every message in the subset of messages that the server provided them (depending on the efficiency of the decryption method).

Usage

Generate a key pair:

use fuzzytags::FuzzySecretKey;
let gamma = 24;
let secret_key = FuzzySecretKey::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

Once in possession of a public key, a party in a metadata resistant app can use it to generate tags:

    use fuzzytags::FuzzySecretKey;
    let gamma = 24;
    let secret_key = FuzzySecretKey::generate(gamma);
    let public_key = secret_key.public_key();
    
    // Give public key to a another party...
    // and then they can do...
    let tag = public_key.generate_tag();

These tags can then be attached to a message in a metadata resistant system.

Testing 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. The server can then test a given tag against the detection key e.g.:

    use fuzzytags::FuzzySecretKey;
    let gamma = 24;
    let secret_key = FuzzySecretKey::generate(gamma);
    let public_key = secret_key.public_key();
    // extract a detection key
    let detection_key = secret_key.extract(5);
    
    // Give public key to a another party...
    // and then they can do...
    let tag = public_key.generate_tag();
    
    // The server can now do this:
    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.
    }

Entangled Tags

When enabled with the entangled feature the FuzzyPublicKey::generate_entangled_tag function is available. This allows you to generate tags that will validate against multiple detection keys from distinct public keys and opens up applications like multiple broadcast and deniable sending.

   use fuzzytags::{FuzzySecretKey, FuzzyPublicKey};
   let secret_key_1 = FuzzySecretKey::generate(24);
   let secret_key_2 = FuzzySecretKey::generate(24);
   let public_key_1 = secret_key_1.public_key(); // give this to a sender
   let public_key_2 = secret_key_2.public_key(); // give this to a sender
   // Will validate for detection keys derived from both secret_key_1 and secret_key_2 up
   // to n=8
    #[cfg(feature = "entangled")]
   let tag = FuzzyPublicKey::generate_entangled_tag(vec![public_key_1,public_key_2], 8);

Benchmarks

We use criterion for benchmarking, and benchmarks can run using cargo bench

Results will be in target/criterion/report/index.html.

Integrating fuzzytags

For more guidance on integrating fuzzytags into a privacy preserving application see documentation

Credits and Contributions

• Based on Fuzzy Message Detection by Gabrielle Beck and Julia Len and Ian Miers and Matthew Green
• Performance & API improvements contributed by Henry de Valence