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
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:
- n=6,\delta=9. Yields maximal n_1=n_2=n_3=3. The effective false positive rate is p_c= 2^{-9}.
- 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.
- Combine the outputs: \vec{m} := \cap_{i\leq d}\vec{m}_i.
- 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. |