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)
An implementation of the FMD2 scheme described in “Fuzzy Message Detection”. Using
Ristretto as the prime order group.
