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.
The paper’s original definition of fuzzy message detection is as a tuple of
(KeyGen, Flag, Extract, Test). The receiver uses
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
This scheme should satisfy certain properties, formalizations of which can be found in the paper:
Valid matches must always be detected by
Test; i.e., there are no false negatives.
Invalid matches should produce false positives with probability approximately , as long as the flag ciphertexts and detection keys were honestly generated.
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.
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
(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
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.
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.