220 lines
10 KiB
Markdown
220 lines
10 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 ("notifications").
|
||
|
||
Many schemes rely on a bandwidth-intensive "download everything and attempt-decryption" approach. Others rely on a trusted
|
||
3rd party, or various non-collusion assumptions, to provide a "private" service. Other schemes
|
||
require that parties arrange themselves in "buckets" or "mailboxes" effectively creating smaller instances of the
|
||
"download everything" approach.
|
||
|
||
It would be awesome if we could get an **untrusted**, **adversarial** server to do the work for us
|
||
without compromising metadata-resistance or requiring parties to split themselves into buckets (effectively
|
||
dividing the anonymity set of the system)!
|
||
|
||
|
||
|
||
**fuzzytags** is an experimental probabilistic cryptographic tagging structure to do just that!
|
||
|
||
Instead of placing messages into deterministic buckets based on the recipient, **fuzzytags** allow each
|
||
message to probabilistically address itself to several parties in addition to the intended party - utilizing the
|
||
anonymity of the whole set of participants, instead of the ones who happen to share a bucket for a given round.
|
||
|
||
Specifically **fuzzytags** provide the following properties:
|
||
|
||
* Correctness: Valid tags constructed for a specific tagging key will always validate when tested using a
|
||
derived detection key.
|
||
* Fuzziness: Tags will produce false positive matches 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**. (this property is referred to as *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 for a given party will be very high.
|
||
|
||
If _p_ is too high, then an adversarial server will be able to link messages to recipients with probability
|
||
approaching _1_.
|
||
|
||
Likewise a large _γ_ means higher bandwidth costs, but a small _γ_ reveals more of the root secret to the server while
|
||
also increasing the change of perfect (but false) matches across all parties.
|
||
|
||
We are also [building a simulator](https://git.openprivacy.ca/openprivacy/fuzzytags-sim) to understand these
|
||
parameter choices in addition to other factors when deploying fuzzytags to real-world systems.
|
||
|
||
For more guidance (and warnings) on integrating fuzzytags into a privacy preserving application see [documentation](https://docs.rs/fuzzytags/#integrating-fuzzytags)
|
||
|
||
## Building
|
||
|
||
This crate requires experimental features currently only provided by Rust nightly:
|
||
|
||
` rustup default nightly`
|
||
|
||
## Terminology and a 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 `RootSecret`, from which they can derive a `DetectionKey` and a `TaggingKey`. 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** `TaggingKey`.
|
||
|
||
All parties will `extract` a `DetectionKey` 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
|
||
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
|
||
|
||
A party first needs to generate `RootSecret`
|
||
|
||
use fuzzytags::RootSecret;
|
||
use rand::rngs::OsRng;
|
||
let mut rng = OsRng;
|
||
let secret = RootSecret::<24>::generate(&mut rng);
|
||
|
||
From the secret detection key a party can derive a `DetectionKey` which can be given to adversarial server to
|
||
fuzzily detect tags on behalf of the party.
|
||
|
||
From the secret detection key a party can also derive a `TaggingKey` that can be public and given to
|
||
other parties for the purpose of generating fuzzytags addressed to a given party.
|
||
|
||
The `24` in the above code is a 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 tagging key, a party in a metadata resistant app can use it to generate tags:
|
||
|
||
use fuzzytags::RootSecret;
|
||
use rand::rngs::OsRng;
|
||
let mut rng = OsRng;
|
||
let secret = RootSecret::<24>::generate(&mut rng);
|
||
let tagging_key = secret.tagging_key();
|
||
|
||
// Give public key to a another party...
|
||
// and then they can do...
|
||
let tag = tagging_key.generate_tag(&mut rng);
|
||
|
||
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::RootSecret;
|
||
use rand::rngs::OsRng;
|
||
let mut rng = OsRng;
|
||
let secret = RootSecret::<24>::generate(&mut rng);
|
||
let tagging_key = secret.tagging_key();
|
||
// extract a detection key
|
||
let detection_key = secret.extract_detection_key(5);
|
||
|
||
// Give the tagging key to a another party...
|
||
// and then they can do...
|
||
let tag = tagging_key.generate_tag(&mut rng);
|
||
|
||
// 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 `TaggingKey::generate_entangled_tag` function is available. This
|
||
allows you to generate tags that will validate against **multiple** detection keys from **distinct tagging keys** and
|
||
opens up applications like **multiple broadcast** and **deniable sending**.
|
||
|
||
|
||
use fuzzytags::{RootSecret, TaggingKey};
|
||
use rand::rngs::OsRng;
|
||
let mut rng = OsRng;
|
||
let secret_1 = RootSecret::<24>::generate(&mut rng);
|
||
let secret_2 = RootSecret::<24>::generate(&mut rng);
|
||
let tagging_key_1 = secret_1.tagging_key(); // give this to a sender
|
||
let tagging_key_2 = secret_2.tagging_key(); // give this to a sender
|
||
// Will validate for detection keys derived from both secret_1 and secret_2 up
|
||
// to n=8
|
||
#[cfg(feature = "entangled")]
|
||
let tag = TaggingKey::generate_entangled_tag(vec![tagging_key_1,tagging_key_2], &mut rng, 8);
|
||
|
||
## Serialization
|
||
|
||
This crate relies on `serde` for serialization. FuzzyTags are first compressed into a byte array of 64 bytes +
|
||
`γ` bits, padded to the end with zeros to the nearest byte. This representation can then be exchanged using a number
|
||
of different approaches e.g.:
|
||
|
||
use fuzzytags::RootSecret;
|
||
use fuzzytags::Tag;
|
||
use rand::rngs::OsRng;
|
||
|
||
let mut rng = OsRng;
|
||
let secret = RootSecret::<24>::generate(&mut rng);
|
||
let tagging_key = secret.tagging_key();
|
||
|
||
// Give public key to a another party...
|
||
// and then they can do...
|
||
let tag = tagging_key.generate_tag(&mut rng);
|
||
|
||
// An example using JSON serialization...see serde doc for other formats:
|
||
let serialized_tag = serde_json::to_string(&tag).unwrap();
|
||
println!("Serialized: {}", serialized_tag);
|
||
|
||
// We can then deserialize with:
|
||
let deserialized_tag: Result<Tag<24>, serde_json::Error> = serde_json::from_str(&serialized_tag);
|
||
println!("Deserialized: {}", deserialized_tag.unwrap());
|
||
|
||
## Benchmarks
|
||
|
||
We use [criterion](https://crates.io/crates/criterion) for benchmarking, and benchmarks can run using `cargo bench --bench fuzzy_tags_benches`
|
||
|
||
Results will be in `target/criterion/report/index.html`.
|
||
|
||
To benchmark entangled tags run:
|
||
|
||
`cargo bench --features "entangled" --bench entangled`
|
||
|
||
### AVX2
|
||
|
||
This crate has support for the avx2 under the feature `simd`, to take advantage of this feature it is
|
||
necessary to build with `RUSTFLAGS="-C target_feature=+avx2"` e.g.
|
||
|
||
`env RUSTFLAGS="-C target_feature=+avx2" cargo test --release --features "bulk_verify,entangled,simd"`
|
||
|
||
This results in a 40%+ performance improvements on the provided benchmarks.
|
||
|
||
## Credits and Contributions
|
||
|
||
- Based on [Fuzzy Message Detection](https://eprint.iacr.org/2021/089) by Gabrielle Beck and Julia Len and Ian Miers and Matthew Green
|
||
- Performance & API improvements contributed by Henry de Valence
|
||
- Universal Tag Bug found by [Lee Bousfield](https://github.com/PlasmaPower/)
|
||
- Fuzzytags Logo by [Marcia Díaz Agudelo](https://www.instagram.com/marcia_ilustra/)
|
||
- Thanks to Henry de Valence, George Tankersly, Lee Bousfield and others for helpful discussions. |