Sender and Receiver FMD

The goal of detection capability is to be able to filter the global stream of state updates into a local stream of state updates that includes all updates related to a particular address, without identifying precisely which updates those are. The rate of updates on this filtered stream should be bounded below, to ensure that there is a large enough anonymity set, and bounded above, so that users processing the stream have a constant and manageable amount of work to process it and catch up with the current chain state. This means that the detection precision must be adaptive to the global message rates: if the false positive rate is too low, the filtered stream will have too few messages, and if it is too high, it will have too many messages.

However, this isn’t possible using the paper’s original definition of fuzzy message detection, because the false positive probability is chosen by the receiver, who has no way to know in advance what probability will produce a correctly sized stream of messages. One way to address this problem is to rename the original FMD definition as Receiver FMD (R-FMD), and tweak it to obtain Sender FMD (S-FMD), in which the sender chooses the detection probability.

Receiver FMD

The paper’s original definition of fuzzy message detection is as a tuple of algorithms (KeyGen, Flag, Extract, Test). The receiver uses KeyGen to generate a root key and a flag key1. A sender uses the receiver’s flag key as input to Flag to produce a flag ciphertext. The Extract algorithm takes the root key and a false positive rate (chosen from some set of supported rates), and produces a detection key. This detection key can be applied to a flag ciphertext using Test to produce a detection result.

This scheme should satisfy certain properties, formalizations of which can be found in the paper:

Correctness.

Valid matches must always be detected by Test; i.e., there are no false negatives.

Fuzziness.

Invalid matches should produce false positives with probability approximately , as long as the flag ciphertexts and detection keys were honestly generated.

Detection Ambiguity.

An adversarial detector must be unable to distinguish between a true positive and a false positive, as long as the flag ciphertexts and detection keys were honestly generated.

In this original definition, the receiver has control over how much detection precision they delegate to a third party, because they choose the false positive probability when they extract a detection key from their root key. This fits with the idea of attenuating credentials, and intuitively, it seems correct that the receiver should control how much information they reveal to their detector. But the information revealed to their detector is determined by both the false positive probability and the amount of other messages that can function as cover traffic. Without knowing the extent of other activity on the system, the receiver has no way to make a principled choice of the detection precision to delegate.

Sender FMD

To address this problem, we generalize the original definition (now Receiver FMD) to Sender FMD, in which the false positive probability is chosen by the sender.

Like R-FMD, S-FMD consists of a tuple of algorithms (KeyGen, Flag, Extract, Test). Like R-FMD, KeyGen generates a root key and a flag key, and Test takes a detection key and a flag ciphertext and produces a detection result. Unlike R-FMD, Extract produces a detection key directly from the root key, and Flag takes the false positive rate and the receiver’s flag key to produce a flag ciphertext. As discussed below, S-FMD can be realized using tweaks to either of the R-FMD constructions in the original paper.

In R-FMD, flag ciphertexts are universal with respect to the false positive rate, which is applied to the detection key; in S-FMD, the false positive rate is applied to the flag ciphertext and the detection key is universal. (This means there is no meaningful difference in capability between the root key and the detection key, so the distinction is maintained just for ease of comparison between the two variants).

Unlike R-FMD, S-FMD allows detection precision to be adaptive, by having senders use a (consensus-determined) false positive parameter. This parameter should vary as the global message rates vary, so that filtered message streams have a bounded rate, and it should be the same for all users, so that messages cannot be distinguished by their false positive rate.

1

The paper calls these the secret and public keys respectively, but we avoid this in favor of capability-based terminology that names keys according to the precise capability they allow.