Determine whether Penumbra could integrate Fuzzy Message Detection

[hdevalence]

Notes on FMD added in 38c921bedfc5d3bd023b8a959ff8cdf7095c2fb0 and (currently) rendered here: https://penumbra.zone/crypto/primitives/fmd.html

That page has a number of questions, copied below:

• How should the false positive rate be determined? In some epoch, let $p$ be the false positive rate, $N$ be the total number of messages, $M$ be the number of true positives for some detection key, and $D$ be the number of detections for that detection key. Then $$ E[D] = M + p(N-M) = pN + M(1-p), $$ and ideally $p$ should be chosen so that:

  1. $E[D]$ is bounded above;
  2. When $M$ is within the range of "normal use", $E[D]$ is close enough to $pN$ that it's difficult for a detector to distinguish (what does this mean exactly?);

• The notion of detection ambiguity only requires that true and false positives be ambiguous in isolation. In practice, however, a detector has additional context: the total number of messages, the number of detected messages, and the false positive probability. What's the right notion in this context?

• What happens when an adversary manipulates $N$ (diluting the global message stream) or $M$ (by sending extra messages to a target address)? There is some analogy here to [flashlight attacks][flashlight], although with the critical difference that flashlight attacks on decoy systems degrade privacy of the transactions themselves, whereas here the scope is limited to transaction detection.

• ~~If a detector has detection keys for both the sender and receiver of a transaction, they will detect the corresponding message with both keys with probability $1$, relative to a base rate of probability $p^2$. How does this affect their information gain? How does this change as the detector has not just two keys, but some proportion of all detection keys? How much more of the transaction graph could they infer?~~

• How are detection keys derived and/or shared, so that they can actually be used by participants in the protocol?

[hdevalence]

Some rough notes towards figuring out how detection keys could be derived/shared:

Because detection is a subcapability of viewing, detection keys should be derived from the incoming viewing key.

The flag keys are quite large (one group element per bit of possible false positive rate), so it would be useful to be able to derive them from some other key material.

Because the FMD constructions are built out of an ambiguous encryption scheme by encrypting each bit of a bloom filter, the components of the flag key and the components of the detection key correspond to each other as the two halves of a keypair for the underlying bit encryption scheme.

A mechanism like BIP32/ZIP32 allows public derivation of child pubkeys from a parent public key using non-hardened derivation. This could potentially be used to derive an arbitrarily-long flag key as a sequence of child pubkeys. However, non-hardened derivation doesn't allow separation of capability, meaning that knowledge of one child secret and the parent public key allows recovery of the parent secret and thus the entire subtree of keys.

For R-FMD, this is a big problem, because R-FMD, the root key has secrets for every bit, and attenuates the capability of a detection key by disclosing only a subset of those components, controlling the false positive rate. However, in S-FMD, the detection key is the entire root key -- since the false positive rate is controlled by the sender, there is no separation of capability. So, S-FMD could potentially derive an arbitrarily-precise flag/detection keypair from a single public / secret keypair, which would be much more compact.

Unfortunately, this keypair cannot be publicly derived from the transmission key / incoming viewing key, because detection should be a strict subcapability of viewing, so it should not be possible to recover the viewing key from the detection key. This means that addresses would need to include a flag key in addition to a transmission key.

Open questions:

• How would this work with diversifiers? Is it possible to tweak the FMD2 construction to detect messages from diversified flag keys, much the same way that it's possible to scan multiple diversified addresses with a single viewing key?
• How would an FMD2 adapted for public derivation of flag key components work, exactly? As written in the paper, the FMD2 construction chooses a random basepoint. Can this be skipped by deriving an additional secret key component?

[hdevalence]

If a detector has detection keys for both the sender and receiver of a transaction, they will detect the corresponding message with both keys with probability $1$, relative to a base rate of probability $p^2$. How does this affect their information gain? How does this change as the detector has not just two keys, but some proportion of all detection keys? How much more of the transaction graph could they infer?

The reason to flag them to the sender would be so that the sender can use FMD to recover their own transactions in case they lost local state. But this is a less common case, and could be accomplished in other ways -- for instance, by providing them a way to check which of their nullifiers have been spent. So it's probably better to avoid this issue by only flagging messages to the receiver's address, not to the sender.

[burdges]

It's not like being "derived" but implicit certificates could prove they were authorized by the viewing key, if you even care about that. It does not have much advantage over a regular certificate though honestly.

[hdevalence]

@burdges Thanks! I think the main motivation for derivation isn't to prove that the detection was authorized by the viewing key, but that there shouldn't be "extra" key material needed to derive the detection keys (so that all of the relevant keys can be derived from the root spending key).

[seresistvanandras]

Interesting questions and super excited to see that you're considering to implement and deploy this in the real-world. I also like FMD and recently am working on a formal privacy analysis of FMD that could be interesting to you.

• How should the false positive rate be determined? In some epoch, let $p$ be the false positive rate, $N$ be the total number of messages, $M$ be the number of true positives for some detection key, and $D$ be the number of detections for that detection key. Then $$ E[D] = M + p(N-M) = pN + M(1-p), $$ and ideally $p$ should be chosen so that:

  1. $E[D]$ is bounded above;

What does this mean exactly? D follows a Binomial(N-M,p) distribution, so in theory even N-M false positives could be really possible, though with low probability.

2. When $M$ is within the range of "normal use", $E[D]$ is close enough to $pN$ that it's difficult for a detector to distinguish (what does this mean exactly?);

I think it is wiser first to consider and define the anonymity/privacy guarantees that we wish to achieve with FMD in your system. In my ongoing analysis I considered 3 such privacy/anonymity notions: Receiver unlinkability, relationship anonymity and protecting the number of incoming messages from the server (spoiler: this could be easily analyzed in a differentially private setting).

Given the definitions of these notions, we can define adversaries that can break these anonymity notions. Their success probabilities in breaking these guarantees can give good indications, regimes for choosing the false positive rates accordingly. I can show you my results I achieved so far if you're interested, or I'd be happy to hop on a call to discuss and hear your inputs, or I can just send the draft of my paper.

• The notion of detection ambiguity only requires that true and false positives be ambiguous in isolation. In practice, however, a detector has additional context: the total number of messages, the number of detected messages, and the false positive probability. What's the right notion in this context?
• What happens when an adversary manipulates $N$ (diluting the global message stream) or $M$ (by sending extra messages to a target address)? There is some analogy here to [flashlight attacks][flashlight], although with the critical difference that flashlight attacks on decoy systems degrade privacy of the transactions themselves, whereas here the scope is limited to transaction detection.

Relationship anonymity is quite brittle in FMD. Therefore this attack of diluting messages, i.e. multiple messages between a fixed sender and recipient is quite easily detectable with statistical tests (Z-test or t-test). Something along these lines were already observed by Sarah Jamie Lewis.

• ~If a detector has detection keys for both the sender and receiver of a transaction, they will detect the corresponding message with both keys with probability $1$, relative to a base rate of probability $p^2$. How does this affect their information gain? How does this change as the detector has not just two keys, but some proportion of all detection keys? How much more of the transaction graph could they infer?~

Sarah made some preliminary simulations where she was able to recover quite a lot edges in the relationship graph. I also made some simulations and slightly improved Sarah's results with fancy statistical analysis.

[hdevalence]

and ideally $p$ should be chosen so that:

1. $E[D]$ is bounded above;

What does this mean exactly? D follows a Binomial(N-M,p) distribution, so in theory even N-M false positives could be really possible, though with low probability.

Sorry for being unclear, these notes are still pretty rough. Yes, D follows a binomial distribution, so D itself could be quite large (with low probability). But the goal is to bound E[D] above, so that clients have (in expectation) a fixed amount of work to do to scan messages. This goal is in tension with (and is secondary to) the goal of protecting information about user activity.

1. When $M$ is within the range of "normal use", $E[D]$ is close enough to $pN$ that it's difficult for a detector to distinguish (what does this mean exactly?);

I think it is wiser first to consider and define the anonymity/privacy guarantees that we wish to achieve with FMD in your system. In my ongoing analysis I considered 3 such privacy/anonymity notions: Receiver unlinkability, relationship anonymity and protecting the number of incoming messages from the server (spoile: this could be easily analyzed in a differentially private setting). ... I can show you my results I achieved so far if you're interested, or I'd be happy to hop on a call to discuss and hear your inputs, or I can just send the draft of my paper.

Yes, this point is just supposed to be a placeholder for defining those notions; I'd be happy to take a look at your draft.

• ~If a detector has detection keys for both the sender and receiver of a transaction, they will detect the corresponding message with both keys with probability $1$, relative to a base rate of probability $p^2$. How does this affect their information gain? How does this change as the detector has not just two keys, but some proportion of all detection keys? How much more of the transaction graph could they infer?~

Sarah made some preliminary simulations where she was able to recover quite a lot edges in the relationship graph. I also made some simulations and slightly improved Sarah's results with fancy statistical analysis.

Cool, I'd be interested to see it. That specific point is crossed out because it's a concern related to a now-discarded idea for applying FMD. Penumbra's use of FMD would be different from the scenarios considered in a more conventional messaging system (although the capabilities of a detector are TBD), and in particular:

• detection is not performed by a central server, but by potentially multiple detectors;
• a detector only has access to data included on-chain (which does not include sender metadata);
• a detector has only a subset of detection keys, not all users' detection keys, and does not know how many users or detection keys exist in total;
• even if multiple detectors collude, some users do not use any detector.

This means that some of the analysis does not apply: for instance, @s-rah 's trivial attributions are messages that are detected by only one detection key. Each honestly generated message is a true positive for some detection key, so when a central server has all users' detection keys, the detector can attribute that message as a true positive for that detection key. But this is only possible in the "closed-world" setting where a single detector has all of the detection keys; in an "open-world" setting where a detector operates on behalf of some strict subset of users, trivial attribution is not possible, because the message could be a true positive for some unknown detection key.

In general, I think it's extremely difficult to draw conclusions about the privacy properties of FMD in general, as those properties depend pretty critically on the details of how the primitive is integrated into a larger system. Hopefully the details of how FMD would be integrated into Penumbra can be nailed down soon to get a sense of what the privacy properties are for Penumbra.

[seresistvanandras]

This idea of delegating the detection to multiple non-colluding servers is an interesting enhancement over the original "closed-world" FMD scheme at the expense of added trust assumptions though. Either way, from a theoretical point of view, I think it makes perfect sense to analyse FMD in the "closed-world" model.

I think the interesting aspect of the FMD privacy guarantee question is that this privacy-enhancing protocol is going to be embedded in an anonymous communication (messaging) system. Hence, also the desired privacy guarantees need to match the specifics of the application where FMD is applied. IMO the most important question is what kind of privacy and anonymity guarantees we want to achieve in our specific context.

Note that also Bloom-filters provide dynamic k-anonymity, however, their privacy guarantees were not examined in the context of anonymous communication systems. Though, this paper is relevant and a great read.

These are the major privacy guarantees I was working with so far:

• Receiver unlinkability The server should not be able to tell whether 2 messages are sent to the same user or not. Receiver unlinkability is of utmost importance to hold, because if it does not hold then it allows the server to natively link messages and launch intersection attacks on its users. So, we better want to achieve receiver unlinkability and we need to choose false positive rates accordingly to avoid likability attacks!
• Relationship anonymity We also want to protect the relationships of communicating parties. The server can reconstruct quite a portion of the social graph if a fixed sender and receiver exchange multiple messages between each other which is most likely the case in a payment system or in an instant messaging application.
• Protecting the number of incoming messages The server as well as a local passive adversary (e.g., an ISP) could observe the number of messages/flag ciphertexts a client downloads. How much information is leaked/ privacy is lost by seeing the number of incoming flag ciphertexts? Ideally, no one should know how many real message/payment/transaction a client received. One can model the incoming flag ciphertexts of a user as real messages + Gaussian noise, more precisely, in(r)+Binom(N-in(r),p) and the second term can be well approximated by a Gaussian distribution. So this property can be nicely analyzed in a (local) differential privacy framework. For details, see the draft I sent you :)

Is there any other notion of privacy and/or anonymity we wish to protect? Is there anything that comes to your mind and I missed?

[hdevalence]

This idea of delegating the detection to multiple non-colluding servers is an interesting enhancement over the original "closed-world" FMD scheme at the expense of added trust assumptions though. Either way, from a theoretical point of view, I think it makes perfect sense to analyse FMD in the "closed-world" model.

There's no added trust assumptions, just a better modeling of the real system. It's not necessary to model multiple detection servers, only a single detection server that has only a strict subset of the detection keys. The problem with the closed-world model is that it's not like the real system, and analysis of a closed-world model doesn't carry over to the open-world system that would actually be used in Penumbra. So I'd be interested in looking at the open-world model.

I think the interesting aspect of the FMD privacy guarantee question is that this privacy-enhancing protocol is going to be embedded in an anonymous communication (messaging) system. Hence, also the desired privacy guarantees need to match the specifics of the application where FMD is applied. IMO the most important question is what kind of privacy and anonymity guarantees we want to achieve in our specific context.

Yes, unfortunately it's not really possible to do this for Penumbra yet, because the rest of the system design hasn't been worked out yet. It could be good to come back to it in a few months.

• Relationship anonymity We also want to protect the relationships of communicating parties. The server can reconstruct quite a portion of the social graph if a fixed sender and receiver exchange multiple messages between each other which is most likely the case in a payment system or in an instant messaging application.

I sent some comments on your draft by email, but I'm not sure this conclusion holds in general. I don't think it holds for Penumbra.

• Protecting the number of incoming messages The server as well as a local passive adversary (e.g., an ISP) could observe the number of messages/flag ciphertexts a client downloads. How much information is leaked/ privacy is lost by seeing the number of incoming flag ciphertexts? Ideally, no one should know how many real message/payment/transaction a client received. One can model the incoming flag ciphertexts of a user as real messages + Gaussian noise, more precisely, in(r)+Binom(N-in(r),p) and the second term can be well approximated by a Gaussian distribution. So this property can be nicely analyzed in a (local) differential privacy framework. For details, see the draft I sent you :)

Note that messages and flag ciphertexts aren't interchangeable here: messages are variable-length payloads that the flag ciphertexts are supposed to filter. Assuming that the detection server uses transport encryption, and a reasonable network protocol that bundles messages and flag ciphertexts, a passive adversary has to solve a knapsack problem to work backwards from a total payload size to possible combinations of messages.

That said, for this issue, network privacy is out-of-scope -- that's a whole separate layer to work through, this issue is just focused on integrating message detection into the protocol, and considering what a detector could see.

[seresistvanandras]

Thanks for the clarification, now I see what is the real difference between the closed- and the open-world model. I concur that the open-world scenario is most likely closer to a real-world deployment of the FMD protocol. I agree that receiver unlinkability is better in the open-world model, since the server cannot observe many potential recipients of a message. Hence it is less likely that the sets of potential recipients will intersect. Although, my gut feeling is that most of the observations made in the draft with respect to relationship anonymity and the number of incoming messages are still applicable in the open-world scenario because those notions of privacy solely focus on a single recipient (protecting the number of messages) or a fixed pair of a single recipient and a sender (relationship anonymity).

Hmmmm....if messages are variable-length, then you're right and indeed an ISP would have a hard time in establishing the number of downloaded messages, namely as you observe need to solve a nasty knapsack problem. Maybe, in a blockchain application where you download transactions (let's say Bitcoin/Ethereum (Umbra) stealth transactions) from the untrusted server, we could assume that the messages have kind of the same size?

Yeah, I don't want to bring here the gross and anyways orthogonal problem of network privacy. I just wanted to better understand the attacker/threat model of FMD by assuming that a local passive adversary might know the number of downloaded messages or flag ciphertexts and from that, it could potentially figure out the number of incoming messages. I also want to give a thought to other potential adversaries in the protocol, e.g., what could a corrupted recipient do?

Thanks for the comments and really looking forward to discussing these with you in more detail!

[hdevalence]

Closing this as resolved, since we will integrate FMD, though parameter selection is TBD.