FMD+TEE proposal: threat model, parameters and requirements

The purpose of this post is to discuss and concretize the threat model, the parameters (what are they, which are system parameters and which are receiver-defined), and the requirements and features we want to offer with the FMD+TEE proposal.

The content of the draft below is subject to change/add/delete based on the ongoing discussion.

Changelog

  • 29/01/2025:
    • Renamed “relayers” to “solvers”.
  • 05/02/2025:
    • \gamma as a global parameter.
    • Sync happens over batches of fixed size s. It assumes stored messages can be ordered canonically.
    • Split users into senders and receivers. Receivers set their own false-positive rate.
    • Clarified receiver detection rate. (An overall leaked rate.)
    • Refined requirements: clearer goals, and distinguished scope of enforcement.
    • Simplified model:
      • Removed solvers. As of now paused but see end of the post for more on this.
      • Communication: sender -> storage pools -> detection servers -> receiver
      • One corruption threshold (instead of two).
      • Removed system and receiver anonymity metrics. (It was confusing.)
    • Description of receiver’s operations (key split and output combine)
    • Included flow diagram
  • 07/02/2025
    • Added forward secrecy to requirements. To account for it, honest erasures are allowed in the threat model.
    • Dishonest senders or receivers postponed for a more refined threat model.
    • global parameter d is a lower bound on number of servers.

Ongoing discussion

Current discussion points.

Temporary corruptions

The adversary can corrupt detection servers for a fixed period of time. After, the adversary looses control, and the server becomes honest again.

This is a weaker adversary than the currently considered. On the good side, receivers can increase their leaked detection rate, as now is harder to corrupt more than t servers at the same time.

With temporary corruptions we can achieve backward secrecy by rotating keys.

Backward secrecy: If the adversary corrupts a detection server at time t_c, the identity of recipients of messages send at some future time t> t_c is not leaked.

Persistent storage of detection keys

Not explicitely stated in the current draft whether detection keys are sent by receivers on each request, or they are stored permanently by the detection server.

Note: If sent by receivers on each request, key-rotation is simplified.

All detection-positives to receivers

How can we ensure a given detection server does not drop detection-positives (both false and true positives) from their outputs?

If we are going to combine outputs, the receiver takes the intersection of the servers’ output, and runs trial-decrypt on it.

Attack: A malicious server can exclude a detection-positive from its output, so it won’t go to trial-decrypt.

We can include one of these two requirements (ideally, the first one):

Description Scope What for How to achieve it
1. Detection servers run FMD detection and send the result to receivers. System-enforced Robustness TEE attestation. (Defense-in-depth, breaks if TEE compromised.)
2. Detection servers that drop detection-positives are eventually caught. User-enforced Robustness See below.

To enforce requirement 2:

  • The obvious way is to run full trial-decryptyon from time to time :frowning: But it is unclear how a receiver can convince that the server was dishonest without disclosing their message, and defeats the purpose of FMD filtering.
  • Somehow replicate detection keys across servers. If there is a disagreement on the received messages, then something wrong happened.

Recipient unlinkability

Should we add the following requirement?

Description Scope What for How to achieve it
It is hard to tell whether two messages are addressed to the same recipient System-enforced Privacy. No single detection server has detection keys for all receivers.

Draft

System parties

Storage pools. Public bulletin boards where data is stored. Stored data consists in pairs (m,\vec{f}), the encrypted message m attached with the FMD flag ciphertext \vec{f}. There exists a canonical ordering of the messages that everyone agrees with.

Detection Servers. A fixed set of d servers, responsible for running FMD detection. Each server receives inputs from the storage pools. They send their outputs to receivers.

Senders. They publish encrypted messages to the storage pools with attached FMD ciphertext flags. The encrypted messages are key-private.

Receivers. They receive pairs of encrypted messages/FMD flags from the detection servers. They choose their own FMD false-positive rate.

Threat model

  • The adversary is computationally bounded.
  • The adversary can do active and dynamic corruptions.
  • The adversary can corrupt up to a strict fraction t of the d detection servers. This means that malicious servers may attempt to deviate from the prescribed instructions, or they may leak private receiver information, such as FMD detection keys.
  • Honest detection servers can erase part of their internal state. Erased data is not accessible by the adversary if the server is corrupted later on.
  • The adversary cannot corrupt senders, receivers, or the storage pools.
  • The adversary can observe all network traffic.

Requirements and features

We distinguish two scopes of enforcement:

  • System-enforced: The requirement applies globally (to all receivers).
  • User-enforced: The requirement is enforced by the receiver. Thus, it is optional.
Description Scope What for How to achieve it
The adversary cannot modify nor inspect plaintext data flowing between honest parties. System-enforced. Privacy. Confidential and authenticated channels.
If less than td detection servers are corrupted, then it is guaranteed that the leaked false-positive rate is higher than a rate p_l, chosen by the receiver. User-enforced. Privacy. Receiver splits the detection key among at least (t+1)d detection servers.
Forward secrecy. If the adversary corrupts a detection server at time t_c, the identity of recipients of messages sent at some past time t < t_c is not leaked. User-enforced. Privacy. Receivers rotate detection keys from time to time. Honest servers erase rotated keys.
Receivers get a filtering of all messages in the storage pool. (Possibly at false-positive rates even higher than p_l.) User-enforced. Robustness. Receiver splits among all available servers. (At least one detection server is honest.)
Receivers do not get messages that are not in the storage pools. System-enforced. Robustness. Authenticated channels (storage pools sign messages).
Receivers have an effective false-positive rate lower than the leaked rate p_l. User-enforced. Efficiency. Disjoint split and combining outputs from different servers.
Compact representation of the FMD public keys: The size of the compact key is independent of the \gamma parameter. System-enforced. Efficiency. With public derivation of the FMD public keys.
Diversified detection: A receiver controlling several addresses assigns different FMD public keys to each address, but all share the same FMD detection key. System-enforced. UX. With a diversification strategy

Parameters

Global parameters. Fixed for all parties in the system.

  • pp_\mathsf{fmd}. The public parameters of the FMD scheme. We will settle for the FMD2 scheme of the original paper of Beck et. al., possibly with some tweaks and enhancements. The public parameters include a security parameter \lambda, the description of a group \mathbb{G} of prime order q(\lambda), and a fixed basepoint G\in\mathbb{G}.

  • \gamma\in\mathbb{N}^+. Determines the minimum false-positive detection rate p_{min}:=2^{-\gamma}, and the bitsize of the FMD
    keys (\mathcal{O}(\lambda \gamma) bits) and ciphertext flags (\mathcal{O}(\lambda+\gamma) bits).

  • s\in\mathbb{N}^+. The batch size. The assumption that messages can be canonically ordered in the storage pools allows to split the messages into batches of size at most s.

  • d\in\mathbb{N}^+. A lower bound on the number of detection servers.

  • t\in[0,1). A corruption threshold. The fraction of detection servers controlled by the adversary.

Receiver parameters. Customizable by each receiver r.

  • \ell\in\mathbb{N}^+. The last number of batches to sync from. Each batch is of size exactly s. Note that, if at the moment of sync, there is a total of t messages in the storage pools, the total number of batches is given by the quotient of the integer division t/s := b s +r, where s is the batch size (a global parameter). There are b+1 batches. Each of size s except possibly the last one (of size r<s). The sync is done over the last \min \{\ell,b\} batches of size exactly s.

  • n\in[1,\gamma]. Determines the leaked false-positive detection rate, which is p_l:=2^{-n}.

  • \delta\in[n,\gamma]. The number of private keys shared with detection servers. Determines the effective false-positive rate.

We’d like n low for privacy, and \delta high for efficiency.

Receivers publish their FMD public keys (\gamma points in \mathbb{G}), and split their FMD secret keys (\gamma scalars) among the d detection servers. The split determines bandwith detection server -> receiver.

Operations on the receiver side

Splitting the secret key (sk_1,\ldots,sk_\gamma)

Fix first the leaked false-positive rate n and number of shared private keys \delta. Then, based on the number d of detection servers and the threshold parameter t, find n_1,\ldots,n_d such that

  • \sum_{i\leq d} n_i = \delta,
  • \sum_{(j\leq t)} n_{i_j} \leq n for each subset index (i_1,\ldots,i_t).

The detection key of the i-th server are the n_i private keys (sk_i,\ldots,sk_{i+n_i-1}). Thus, it is a disjoint split.

For example, for global choices d=3,t=2,\gamma=9, a receiver may set:

  1. n=6,\delta=9. Yields maximal n_1=n_2=n_3=3. The effective false positive rate is p_c= 2^{-9}.
  2. n=3,\delta=4. Yields maximal n_1=n_2=1, and n_3=2. The effective rate is p_c=2^{-4}.

Option 1 is biased towards efficiency, and option 2 biased towards privacy. Also, note the asymmetry of option 2, the receiver may share two private keys with a detection server they trust most.

Combining shares and trial decryption

Let \vec{m}_1,\ldots,\vec{m}_d be set of messages that a receiver gets from the d detection servers.

  1. Combine the outputs: \vec{m} := \cap_{i\leq d}\vec{m}_i.
  2. Decrypt each message m\in\vec{m}.

Flow diagram

Old: Model with solvers

The model above can be augmented to account for solvers. (We keep it here for historical reasons, but it is not part of the draft.)

A new role is added to the parties: the solvers. Senders delegate message’s creation and delivery to solvers.

The adversary capabilities are augmented with:

  • Solvers can post messages and FMD flags anonymously in the storage pools.
  • The adversary can control all solvers.
  • Solvers controlled by the adversary may deviate from the prescribed instructions. In particular they may generate incorrect FMD flags.
  • Solvers controlled by the adversary are trusted for privacy. They will not reveal sender or receiver identities.

A new requirement is added:

Description Scope What for How to achieve it
Solvers create and flag messages correctly. System-emforced. Robustness. Zero knowledge proofs.
1 Like

Why did we rename solvers to relayers? I’m not sure that having multiple names is helpful

Also I think it might be more intuitive if we explicitly separate Anoma and Namada cases rather than marking solvers as optional. Marking them as optional kind of implies that we can also have them for Namada, which is confusing. Another reason is that we might need more than solvers to cover Anoma case: for example, global parameters in the Anoma case are set per RM, but we might also have different threat models. Maybe we can handle these cases explicitly for now, and generalise it in the ART report (e.g., introduce relayers in the general model and then say that solvers take on the relayer model in the Anoma case, but the general model would be a report feature only)?

Wouldn’t it be more helpful to split these roles, since they perform quite different tasks in these context? Sure, users can be both senders and receivers, but we have different assumptions holding for different roles.

Do we actually expect it to be fixed or can they join and leave dynamically, given they go through some verification process?

The role distinction would be helpful here: the parameters are chosen by receivers.

I thought gamma is a global parameter? At least I remember discussing it being a consensus parameter.

Perhaps we should explicitly state that detection rate is set per detection server

This is also rather receiver anonymity

I’m not sure we are actually assuming that

This is also rather a strong assumption

Why are we assuming that?

Thanks for the write-up! Some questions from my end:

Do we need to fix this for all users in the system? I think it would be preferable to allow users to choose their detection servers (where different users can make different choices), such that users could choose detection servers they have some reason to trust (e.g. perhaps the same validator(s) to which they have delegated).

Can this be per-unit-time, or does it have to be a fixed number for all time (in which case we’d have to pick a very large one)? From your descriptions below I infer that we’re just analyzing the user anonymity and system anonymity at a particular point in time, which makes sense to me, but I think we’d benefit from making that more explicit.

It would be more realistic to say that the adversary cannot control more than a fixed fraction of the users (senders and receivers), and more realistic still to say that the adversary can control a variable fraction of the users, but that doing so carries a cost (practically, transaction fees). Would this make the analysis far more complex?

What is “the system” here? Do you mean that an adversary may observe all network traffic?

I think it might be easier to first attempt a full, clear model without solvers – at least intuitively to me the addition of solvers shouldn’t change too much of the FMD/TEE-specific aspects of this model, and if we really want a useful model of solvers, we’ll need a more sophisticated one (which I don’t think we need to develop right now).

Thanks for your comments @vveiln and @cwgoes. I have updated the draft based on your input, and also added some other things. We can discuss in the next meeting.

Answers to your questions below.

Changed now.

Yes, it’s clearer. Changed now.

Actually, not entirely sure. We do not assume the identities are fixed, but the number of servers is fixed. I’m doing this way at least for ease of exposition. We may be able to let the number be dynamic probably. Let’s re think.

You are right. Changed to global parameter.

It is now the overall leaked false-poistive rate. It accounts for all the keys shared among servers.

Regarding comments about solvers: I have removed solvers from the draft.

This is related to Yulia’s question. See my answer above.

I have removed anonymity metrics for the sake of simplicity. Users now sync messages over batches of fixed size s.

Hmm, I think the analysis would be more complex, yes. I have added this point to the ongoing discussion list.

Yes, exactly. Hopefully is clearer now.

Agreed. (Also Yulia’s comment.) Solvers are not part of the model any more.

2 Likes