FMD + TEE for private state sync proposal

[vveiln]

This post is just an inspired draft of an idea without concrete estimations and algorithms. The prompt in my head was “what would be a cool solution”, so further investigation required to know if “cool” is also possible and makes sense.

The general idea is to run Penumbra style FMD in TEE, possibly with a separate decryption layer, also in TEE:

• detection layer scans the pool of state updates and returns the relevant state updates + some false positives. We can increase the rate of false positives to have better privacy on this layer
• decryption layer decrypts the detected state updates and filters out the irrelevant ones

Privacy measures:

• TEE: running the computations in TEE allows to transfer the trust assumptions from the compute service providing computational power to the TEE provider. It is assumed to be better
• Tweaking false positive rate: increasing the detection false positive rate implies more computation for the decryption layer but better privacy against the detection layer. In case the decryption layer is not run by the user, we can optimise for overall latency because we are not so limited in computational power. In case it is run by the user, then the main question is how much decryption can the user handle. Higher false positive rate → better privacy.
• Key ratcheting (Signal’s Double Ratchet Scheme) / rerandomization: mostly thinking about it for decryption keys now, but can probably also applied to detection keys (we can investigate). The way it would work is that our decryption key is only valid for a short amount of time after which a new key produced with the help of a one-way function. The old key becomes invalid. The decryption layer then would have to obtain the new key to perform decryption. That allows to increase the cost of TEE attacks.

One of the challenges with key rotation is how to make the old key invalid:

• rerandomization would update the keys but not invalidate the old keys by default and we would need to come up with some solution to achieve that
• ratcheting would invalidate the old keys but requires encrypting the plaintext with the new key, meaning we need replicated ratcheting mechanisms on both sender and receiver sides, which might be difficult. On the other hand, it works fine on Signal and what we are doing isn’t that different from messaging (this article nicely describes the relationship). The sender already needs to get a receiver’s key from somewhere to encrypt the data, so building a ratcheting mechanism on top of that doesn’t sound crazy

[cwgoes]

Questions from discussion:

1. Can we stack multiple detection layers (successively narrowing down to a lower false positive rate)?
2. Can we implement some kind of ratcheting for the detection keys?
3. What sorts of protocols would we need for the TEE servers? Do we have a good understanding of the computational power required here?

[kike]

Here are some thoughts on the proposal.

Stacked filtering

Can we stack multiple detection layers (successively narrowing down to a lower false positive rate)?

I think it would be possible using either FMD1 or FMD2 constructions from FMD paper, Section 5.

For FMD parameter \gamma, we would have a detection layer of \gamma TEE nodes. Filtering is sequential, starting with the public shielded state pool \mathsf{BB}_0. Each node filters the output of the previous node at rate p=1/2. Overall rate would be 2^{-\gamma};, i.e. the smallest possible rate.

• receiver keypair (pk_1,sk_1),\ldots (pk_\gamma,sk_\gamma)
• flag ciphertexts f_m:=(ct_1,\ldots,ct_\gamma) for shielded private state m published in the shielded state pool \mathsf{BB}_0
• node i\in[\gamma] is given detection key (i,sk_i) and filters \mathsf{BB}_{i-1}

Node i filters out \mathsf{BB}_{i-1} by decrypting ct_i using sk_i. Results in \mathsf{BB}_{i}\subseteq\mathsf{BB}_{i-1} containing only pairs (m,f_m) with decryption matching bit 1. \mathsf{BB}_\gamma contains all receiver private states + false positives at the lowest rate p=2^{-n}.

Avoiding correlating private state across users
If a single TEE holds detection keys for all users, then compromising the TEE can trigger correlation attacks across users private states.

To make this harder, split users detection keys evenly across multiple TEEs. Thus, a single TEE holds only a fraction of the total detection keys. Credits to this TEEs Penumbra brainstorming.

Making detection keys useless in the public shielded state pool \mathsf{BB}_0
This is blurry, but might be worth exploring. The idea is to use a mix layer before running through the detection layer.

• sender puts the flag ciphertext f_m in a ‘locked box’ in \mathsf{BB}_0.
• unlock the boxes by passing \mathsf{BB}_0 through a mix-and-rencrypt layer. The output would be pool a \mathsf{BB}'_0 with all shielded states m_i locked in boxes (encrypted under receiver’s key), and all flag ciphertexts unboxed (decrypted) under the joint decryption key of the mix nodes
• pass \mathsf{BB}'_0 to the detection layer

The claim/goal is that at the detection layer, nodes can identify receiver’s private states using the unboxed flags, but do not know to which private states belong in \mathsf{BB}_0. Thus, a compromised detection key cannot be used to test in \mathsf{BB}_0. An attacker would need to compromise all mixing nodes to correlate. Otherwise, only an upper bound of the receiver’s private state is leaked.

[kike]

I’m collecting here some insights from this paper. They may be helpful to design the solution (see countermeasures below).

Recipient unlinkability captures the (in)ability to relate resources consumable by the same user. The adversary is allowed to observe the network, i.e. traffic involving the servers and the private state pool \mathsf{BB}_0. A specific attack vector inspects the anonymity sets of any two shielded resources to infer whether they are consumable by the same user. In the paper, the authors show that the adversary success is lower bounded by (a negligible function in) the number of users whenever the false-positive rate is the same for all users. The smaller these are, the easier to break recipient unlinkability.

Relationship anonymity says that it is not possible to determine the creator and the consumer of a resource. If for any reason the creator and the number of resources it created are known to the servers holding the detection keys, the relationship can be inferred by looking at how many flag ciphertexts a consumer downloads from a given creator.

Temporal detection ambiguity The servers should not be able to tell whether they found a true or a false positive match in a given time interval. In our case, in a given slot of locations of \mathsf{BB}_0. It seems that if the false positive rate is small, then temporal detection is possible. Indeed, one can deduce the probability distribution of false positives (according to the paper, it is a binomial distribtuion). If the actual number of consumable resources for the user is large, then the distribution over false positives can be approximated with a normal distribution. One can now look at the number of downloaded ciphertexts (or passed to the decryption layer), to see if they are statistically close or far to the approximated normal distribution. This tells whether or not in that time interval the downloaded resources contain consumable resources by the user or not.

Countermeasures that we could implement

Split user anonymity set view. A countermeasure for the recipient unlinkability attack is to split the anonymity set view. Since each server holds only a partial view, to launch the attack all servers that jointly hold the view should be compromised. For example, to split the view in the stacked filtering approach, we can have a layered arrangement: servers in the i-th layer split their output and send it to different nodes at the i+1 layer. (This protects against the servers themselves, encrypted communication protects the anonymity set against eavesdroppers.)
Note: I think this may also protect against other traffic inspection attacks. Again, in the stacked filtering toplogy, a server has a single decryption key, but with a straight-line arrangement, it is effectively given a set of filtered ciphertexts at lower false-positive rates.

Flag ciphertexts in the shielded private pool. Attacking relationship anonymity should not be an issue as long as the resource creator remains anonymous. Thus, as long as either of the following holds:

• the flag ciphertexts f_m are in the public shielded state pool \mathsf{BB}_0. This assumes that it is hard to tell apart resources’s creators by looking at \mathsf{BB}_0.
• the sender communicates anonymously to the servers their flag ciphertexts f_m.

Append dummy traffic. To avoid temporal detection ambiguity, servers could append dummy data to their filtered/decrypted ciphertexts. This would have the effect of downloading as with large false positive rates. Communication bandwidth degrades, but users do not need to trial-decrypt to discard the dummy data.

[cwgoes]

Questions from discussion 2024.12.17:

• Should we attempt to verify/constrain the clue (to avoid griefing attacks where a dishonest sender sets an incorrect clue)?
  • If we have to run trial decryption anyways, latency / efficiency guarantees kinda revert to just running trial decryption where FMD “works sometimes”.
  • What we need is more like “verifiable FMD”
  • May need to blind public keys or such for privacy
• Concept of a recipient (account? address?) that includes detection keys
• Most important aspect of first proposal is a single detection layer that can run FMD in a TEE with the right cryptography and some proof that the clue is correct.
• Would be really helpful to clarify the boundaries around network privacy + what assumptions we are or are not able to make.

[kike]

Basic proposal

Based on our discussions, here is a first proposal for prototyping.

0. Building blocks

Fuzzy message detection

We use the IND-CCA secure construction FMD2 := (\mathsf{KeyGen},\mathsf{Flag},\mathsf{Extract},\mathsf{Test}). The flags are ciphertexts of 1 under a hash variant of ElGamal with plaintext \mathbb{Z}_2. ElGamal is instantiated over a cyclic group \mathbb{G} of prime order q with generator g. The scheme also uses two random oracles H:\mathbb{G}^3\rightarrow\mathbb{Z}_2, and G:\mathbb{G}\times\mathbb{Z}_2^\gamma\rightarrow\mathbb{Z}_q.

We slightly modify \mathsf{Flag} and \mathsf{Test} algorithms: detection keys are any ordered subset of the \gamma secret keys, along with their indices. Therefore, decryption of the flag ciphertexts is selected acording to those indices. The reason of this tweak is to allow using the filtered output of a TEE as input to another one. (Originally, detection keys are the first n secret keys for false positive 2^{-n}.)

Only the \mathsf{Test} algorithm needs to be implemented in the TEEs. The other algorithms are executed by the party that creates the resource (the sender).

KeyGen

Inputs:

• \gamma\in\mathbb{N}. Determines the range of false positive rates p\in\{2^{-n}\}_{1\leq n\leq \gamma}
• q,g: The order and generator of \mathbb{G} (given by a security parameter)

1. For 1\leq i\leq \gamma sample random x_i\gets\mathbb{Z}_q
2. Output sk:=(x_1,\ldots,x_\gamma) and pk:=(h_1:=g^{x_1},\ldots,h_\gamma:=g^{x_\gamma})

The parameters q,g,\gamma are passed implicitely to the remaining algorithms.

Flag

Input: Public key pk:=(h_1,\ldots,h_\gamma)\in\mathbb{G}^\gamma

1. Sample random r,z\gets\mathbb{Z}_q
2. u:=g^r, w:=g^z
3. For 1\leq i\leq \gamma do:
   a. k_i := H(u,h_i^r,w) // Hash to \mathbb{Z}_2
   b. c_i:=k_i+1 // Arithmetic in \mathbb{Z}_2
4. m:=G(u,c_1,\ldots,c_\gamma) // Hash to \mathbb{Z}_q
5. y:=(z-m)r^{-1} // Arithmetic in field \mathbb{Z}_q
6. Output flag ciphertexts \vec{f}:=(u,y,c_1,\ldots,c_\gamma)

Extract

Inputs:

• sk:=(x_1,\ldots,x_\gamma)\in\mathbb{Z}_q^\gamma
• n\in[1,\gamma]. Yields false positive rate p=2^{-n}
• \vec{i}:=(i_1,\ldots,i_n)\subseteq[1,\gamma]^n. An ordered subset of indices of size n // We add this input.

1. Output detection key \tilde{dsk}:=((x_{i_1},\ldots,x_{i_n}),(i_1,\ldots,i_n))

Test

Inputs:

• Detection key \tilde{dsk}:=((x_{i_1},\ldots,x_{i_n}),(i_1,\ldots,i_n))\in\mathbb{Z}_q^n\times[1,\gamma]^n for some n\leq\gamma
• Flag ciphertexts \vec{f}:=(u,y,c_1,\ldots,c_\gamma)\in\mathbb{G}\times\mathbb{Z}_q\times\mathbb{Z}_2^\gamma

1. m:=G(u,c_1,\ldots,c_\gamma) // Hash to \mathbb{Z}_q
2. w:=g^m\cdot u^y
3. For 1\leq j \leq n do: // Below i_j is an input index, i.e. decrypt ciphertext at position i_j
   a. k_j := H(u,u^{x_{i_j}},w) // Hash to \mathbb{Z}_2
   b. b_j:=k_{i_j}+c_{i_j} // Arithmetic in \mathbb{Z}_2
4. If all b_j=1 output \mathsf{accept}. Else, output \mathsf{reject}.

TEE confidential channels

Explicit confidential and authenticated communication with the TEEs is out of the scope of this proposal. In the algorithms described below it is just assumed to happen ‘under the hood’. Most likely a symmetric/hybrid encryption scheme will be used.

Shielded encryption

Refer to this post for a description of the algorithms (\mathsf{KeyGen},\mathsf{Encrypt},\mathsf{Decrypt}) used in the implementation of the shielded resource machine.

1. Detection layer

The TEE implements \mathsf{AddDetectionKey} and \mathsf{Filter}. Both algorithms have access to an internal table \mathbb{K}_{det} storing pairs of user identifiers and detection keys (\mathsf{uid},\tilde{dsk}), initialized to empty.

AddDetectionKey

• External input: (\mathsf{uid},\tilde{dsk}): // user id, detection keys
• Internal inputs: \mathbb{K}_{det},k_{in}

1. If entry for \mathsf{uid} exists in \mathbb{K}_{det}, or detection key \tilde{dsk} is not in the right domain do nothing
2. Else, add (\mathsf{uid},\tilde{dsk}) to \mathbb{K}_{det}

Alternatively, output a status flag indicating success or failure (leaks user existence).

Filter

• External inputs: \mathsf{uid},m,\vec{f} // user id, message and flag ciphertexts
• Internal inputs: \mathbb{K}_{det}

1. Retrieve \tilde{dsk} for user \mathsf{uid} from \mathbb{K}_{det}
2. If there is no entry in \mathbb{K}_{det} or \mathsf{FMD2.Test}(\tilde{dsk},\vec{f}) rejects, output (\mathsf{no\_match},\bot)
3. Else \mathsf{FMD2.Test}(\tilde{dsk},\vec{f}) accepts. Output (\mathsf{match},\mathsf{uid},m,\vec{f})

If m is sent to the decryption layer, \vec{f} can be excluded from the output. (For simplicty we assume it is always included.)

2. Decryption layer

The TEE implements \mathsf{AddDecryptionKey} and \mathsf{TrialDecrypt} algorithms. Both algorithms have access to an internal table \mathbb{K}_{dec} storing pairs of user identifiers and message decryption keys (\mathsf{uid},sk), initialized to empty.

AddDecryptionKey

• External input: \mathsf{uid},sk // user id and message decryption key
• Internal inputs: \mathbb{K}_{dec}

1. If entry for \mathsf{uid} exists in \mathbb{K}_{dec} do nothing
2. Else, add (\mathsf{uid},sk) to \mathbb{K}_{dec}

TrialDecrypt

• External inputs: \mathsf{uid},m // user id and message
• Internal inputs: \mathbb{K}_{dec}

1. Retrieve sk for user \mathsf{uid} from \mathbb{K}_{dec}. If there is no entry, output (\mathsf{no\_user},\bot) and halt
2. pt\gets \mathsf{ShieldRM.Decrypt}(sk,m) // Get the plaintext of ciphertext m
3. If cannot parse pt as (\mathsf{uid},\star) output (\mathsf{false\_positive},\bot)
4. Else output (\mathsf{true\_positive},m)

We have assumed plaintext message pt is prepended with the user identifier \mathsf{uid}. Any other mean to identify that pt belongs to user \mathsf{uid} can be used.

3. Remarks

• Algorithms \mathsf{Filter} and \mathsf{TrialDecrypt} could have as external input/output an stream of elements. The description above is discretized for simplicity.
• For efficiency, instantiate ElGamal over an elliptic curve (non pairing-friendly!), for example Curve25519. The choice of the exact curve depends on what is supported by the TEE hardware, but the level of security should be at least 128 bits.
• One possibility to instantiate the random oracles H and G is to serialize the elements of the domain, apply a cryptographic hash function defined over bits (SHA2/3, a XOF…), and then truncate appropriately. Use domain separators to differentiate H from G, and enforce full domain hashing for G.

4. Diagram

Another arrangements are possible. For example, a backend service holding a list of user identifiers interacts with the detection layer (instead of the user).

ZKPs of correct flag generation

I am not including this part in the above proposal because I feel it is not mature enough for prototyping (but this is just my opinion).

The problem

The concern is that a malicious resource creator (sender) can send a message m inconsistent with the flag ciphertexts \vec{f}. Thus, the message is addressed to user \mathsf{uid} , but flag \vec{f} is generated with the public key pk of a different user \mathsf{uid}'.

Enforcing consistency

Consistency between m and \vec{f} can be enforced attaching an non-interactive zero-knowledge (NIZK) proof \pi attesting for correct flag generation. Thus, the sender would send the triplet (m,\vec{f},\pi).

Let ciphertext flags \vec{f} for public key pk. Let us set the user identifier to the public key \mathsf{uid}:=pk, and as in the proposal above, suppose m encrypts plaintext (pk,\star) with \mathsf{ShieldRM.Encrypt}.

NP statement
Given public \vec{f}, and encrypted message m as above. Then, \vec{f} is the result of running \mathsf{FMD2.Flag} on input whatever is encrypted in m.

The statement above can be turned into an arithmetic circuit and prove its satisfiability in zero-knowledge.

Optimizations

Use FMD1 construction We can probably use the FMD1 construction from the original paper. To generate an FMD1 flag, everything related to the oracle G and tag w is removed. This means that the resulting circuit to prove in zero-knowledge would be much less heavy.
Note: FMD1 is only IND-CPA secure, but since we are attaching NIZKs involving the c_i, these cannot be modified. More specifically, FMD1+Knowledge-sound NIZKs should yield IND-CCA security (reduce IND-CPA to IND-CCA by answering decryption queries leveraging the knowledge extractor of the NIZK).

IVC-based approach Correct FMD1 flag generation \vec{f}:=(u,y,c_1,\ldots,c_\gamma) from public key pk:=(h_1,\ldots,h_\gamma) actually involves proving statements of the form:

NP statement (FMD1):
Given public c_i,u, encrypted message m and group generator g. Then, the discrete logarithm of u in base g is the same than the discrete logarithm of the preimage under H of c_i-1 in base h_i, where h_i is the i-th public key component encrypted in m.

A total of \gamma statements, one per c_i in \vec{f}. We could recurse and produce a single proof via a commit-and-prove approach to ensure it is used the same discrete logarithm r --the flag ciphertext encryption randomness–.

Random oracle instantiation. The random oracle H could be instantiated with a zk-friendly collision-resistant hash function (e.g. Poseidon, Pedersen).

Questions

• Why is that the sender needs to prove correct flag generation, again? We have discussed this already, but going through it once more won’t hurt. Specially given this seems to require structural changes to resources, and FMD is just one way to speed up message retrieval.
• How public keys relate to user identities? Above I’ve assumed \mathsf{uid}=pk for simplicity. There may be other ways.
• How FMD public keys relate to resources? Above I’ve assumed they are encrypted in m. In principle could be placed somewhere else in the resource, for example, as an explicit field of the resource, or cheaply derived from some field.

[xuyang]

Thank you for the nice post.

@kike

Flag

1. Sample random x,z\gets\mathbb{Z}_q
2. u:=g^r, w:=g^zu:=gr,w:=gz

Is this a typo here? You sample an x in step one, but use r in the following steps.

@kike

Why is that the sender needs to prove correct flag generation, again? We have discussed this already, but going through it once more won’t hurt. Specially given this seems to require structural changes to resources, and FMD is just one way to speed up message retrieval.

The resource structure can flexibly include an additional FMD pk by embedding it in the value field, similar to how we embedded the verifiable encryption pk. In practice, we can add FMD ciphertext generation to the verifiable encryption module to achieve both verifiable encryption and verifiable FMD as your described.
It may also relate to your question of “How FMD public keys relate to resources”

To achieve verifiable flag ciphertext generation in circuits, we must use circuit-friendly fields, groups, and hash functions for FMD, which will introduce some performance loss of detection.

[xuyang]

@xuyang

To achieve verifiable flag ciphertext generation in circuits, we must use circuit-friendly fields, groups, and hash functions for FMD, which will introduce some performance loss of detection.

I can provide more details on this topic. IIUC, the message encryption protocol and the FMD protocol do not need to use the same cryptographic primitives (like finite fields, groups, hashes, etc.). Thus, we can have an independent FMD implementation that serves all different encryption protocols (Namada, Cairo RM, Risc0 RM, Taiga RM). However, zk circuits are sensitive to cryptographic primitives. To achieve verifiable flag ciphertext generation of FMD in circuits, custom FMD versions for RMs may be necessary.

[kike]

Is this a typo here? You sample an x in step one, but use r in the following steps.

Yes, good catch. In step 1 should sample r and z.

The resource structure can flexibly include an additional FMD pk by embedding it in the value field, similar to how we embedded the verifiable encryption pk.

I see. We just need to make sure the FMD public key is encrypted (since presumably it is linked to recipient’s identity).

To achieve verifiable flag ciphertext generation in circuits, we must use circuit-friendly fields, groups, and hash functions for FMD, which will introduce some performance loss of detection.

By performance loss in detection, do you mean zk-friendly H,G are less efficient than non zk-friendly hashes? If so, and if we go with the FMD1 construction then we save the call to hash G in the FMD test. (What I have in mind is FMD1 but re-using randomness r as in FMD2, to not increase the size of the ciphertext flags. Although, this may yield a more expensive proving than the case where each c_i comes with its own randomness r_i.)

[xuyang]

@kike

By performance loss in detection, do you mean zk-friendly H,GH,GH,G are less efficient than non zk-friendly hashes?

Yes, when running the zk-friendly hashes out-of-circuit in the FMD test, they are typically several times(even more) slower than classic hashes like sha2 or sha3

[kike]

@xuyang

I can provide more details on this topic. IIUC, the message encryption protocol and the FMD protocol do not need to use the same cryptographic primitives (like finite fields, groups, hashes, etc.). Thus, we can have an independent FMD implementation that serves all different encryption protocols (Namada, Cairo RM, Risc0 RM, Taiga RM). However, zk circuits are sensitive to cryptographic primitives. To achieve verifiable flag ciphertext generation of FMD in circuits, custom FMD versions for RMs may be necessary.

OK. At some point we should discuss this in more detail.

[vveiln]

@kike

AddDetectionKey

Note: eventually we would probably want to be able to modify/update/delete the set of detection keys associated with each user

@kike

Output (match,uid,m,f)

When we say “output”, where does this output go? To the untrusted part of the server, to the user, what key is it encrypted under?

@kike

Algorithms \mathsf{Filter} and \mathsf{TrialDecrypt} could have as external input/output an stream of elements. The description above is discretized for simplicity.

I feel like it makes sense to keep it simple for the theoretical model, but we also need to describe explicitly how it would work in a real-world-system for our practical setup because the security concerns really matter for how it is done in practice (e.g. if the tee is given each (id, tx) pair separately and the output is observed by the untrusted server or the tee is fed a stream of txs, then it tests each tx for each id and then shares the result directly with the user). I’ll add it to the list of things to specify

@kike

Filter

• External inputs: \mathsf{uid},m,\vec{f} // user id, message and flag ciphertexts

What is m here? Is it the same m as computed in the Test function above? If not, we should have the names different. Whatever it is, it looks like it isn’t used for the computations, we just take it as input and output it again.

@kike

The statement above can be turned into an arithmetic circuit and prove its satisfiability in zero-knowledge.

Note: since it is only relevant to the Anoma/RM case, we would probably include it in the compliance/logic circuit, not as a separate zk proof

@kike

Given public \vec{f} and encrypted message m as above. Then, \vec{f} is the result of running \mathsf{FMD2.Flag} on input whatever is encrypted in m.

\mathsf{Flag} doesn’t seem to compute over the message (only takes public keys as input), so it is either irrelevant at all or we don’t have enough binding to m in the statement

@kike

IVC-based approach

I wonder how well it works within the compl./logic circuit (probably would have to be IVC for the whole circuit, can’t do it for one statement?)

@kike

Why is that the sender needs to prove correct flag generation, again? We have discussed this already, but going through it once more won’t hurt. Specially given this seems to require structural changes to resources, and FMD is just one way to speed up message retrieval.

1. What structural changes to resources are we talking about?
2. We need it because the resource sender (solver) and resource owner (Alice, sending to Bob) are not the same entitiy. The intuition is similar to why we need verifiable encryption, see here: Roles and requirements - Anoma Specification

[vveiln]

Another thing I wonder about is if we could benefit from a design where we don’t store the detection keys in the TEE long-term, e.g. the user gives the TEE the detection keys and a block height (and possibly the block height upper bound) and the TEE checks all transactions from the oldest to the most recent, outputs the result and destroys the keys. I’m not sure about the trade offs in revealing information to the network observers/untrusted server, but this way we don’t store the keys for longer than needed for one detection run

[kike]

@vveiln

Note: eventually we would probably want to be able to modify/update/delete the set of detection keys associated with each user

Yes, that is something that will be needed. (This first proposal focussed only on the basic functionality.)

@vveiln

When we say “output”, where does this output go?

It goes outside the TEE Your question is very valid though, but since I didn’t want to deal with it in the first iteration, I put it under the carpet with an obscure sentence about ‘‘TEEs confidential channels’’.

@vveiln

To the untrusted part of the server, to the user, what key is it encrypted under?

I think that at least the last TEE node of the decryption layer should communicate with users directly using a confidential and authenticated channel (If there is only the detection layer, then the last detection TEE.)

Regarding the TEEs in the detection layer, it will probably depend on the ‘‘topology’’ of the TEE network. See for example the ‘‘stacked filtering’’ approach described in this answer (The depicted diagram of the basic proposal corresponds to a to stacked filtering with two TEEs.

@vveiln

I feel like it makes sense to keep it simple for the theoretical model, but we also need to describe explicitly how it would work in a real-world-system for our practical setup because the security concerns really matter for how it is done in practice (e.g. if the tee is given each (id, tx) pair separately and the output is observed by the untrusted server or the tee is fed a stream of txs, then it tests each tx for each id and then shares the result directly with the user). I’ll add it to the list of things to specify

I’m not sure I understood this question. My point was that for a fixed request of user \mathsf{uid} instead of passing a single flag/message pair (m,\vec{f}), the TEEs could receive a bunch of them as input in \mathsf{Filter} /\mathsf{TrialDecrypt} .

Please, feel free to add the request to the pending list below.

@vveiln

What is m here? Is it the same m as computed in the Test function above? If not, we should have the names different. Whatever it is, it looks like it isn’t used for the computations, we just take it as input and output it again.

m is the encrypted message sent from sender to receiver. It is used in both, detection layer (\mathsf{Filter} algorithm) and in the decryption layer (\mathsf{TrialDecrypt} algorithm).

In the input to the \mathsf{Filter} algorithm, you are right, as described is not used. It can be understood as an indication of whether or not m is filtered out. Imagine the case where c= Enc(\mathsf{uid},m,\vec{f}) is given as input to the TEE from the previous TEE/user. Here Enc provides confidentiality and authenticity. In this case, the TEE first would decrypt c, then ignore m, and use only \vec{f}. (For the case a single message/flag is passed per user request.)

@vveiln

Note: since it is only relevant to the Anoma/RM case, we would probably include it in the compliance/logic circuit, not as a separate zk proof

OK – this is one place where FMD gets into the RM design.

Another possibility is to have a separate proof, which may help to optimize the prover. Also, who verifies the consistency ZKPs? the TEEs?

@vveiln

Flag \mathsf{Flag} doesn’t seem to compute over the message (only takes public keys as input), so it is either irrelevant at all or we don’t have enough binding to mmm in the statement

The binding is the NP statement itself! In the proposal, m is always the encrypted message. I mean, m is the resulting ciphertext.

Say m =\mathsf{ShieldRM.Encrypt}((pk_{fmd},\star)), where \star is whatever (plaintext) message the sender is sending to receiver with FMD publick key pk_{fmd}. The consistency NP statement on public input (m,\vec{f},pk_{shield}) and witness (pk_{fmd},r) says that the encrypted pk_{fmd} in ciphertext m was used to produce the flag ciphertexts \vec{f}. The statement also proves m is a correct encryption under public key pk_{shield} and randomness r – but I omitted that in the informal description as its is not the essential bit. (Note pk_{fmd} can’t be in the clear in the sent message, as that would allow everyone to identify the receiver.)

So this another place where FMD gets into the RM design. How do users identify messages are for them after they decrypt m? The basic proposal above assumes a shielded encryption of (pk_{fmd},\star). Or we could also have an encryption of the hash of the FMD public key, or could also privately embed the public key in a different field of the Resource Object, or…

@vveiln

I wonder how well it works within the compl./logic circuit (probably would have to be IVC for the whole circuit, can’t do it for one statement?)

If we integrate the consistency statement into the compl/logic statement, then we need to think how to do an IVC as a whole (which is something I briefly thought about for ‘‘logic’’ proofs). As I already commented above, this is one of the reasons to have separate consistency proofs: to optimize proving time via IVC.

@vveiln

What structural changes to resources are we talking about?

Mentioned above: (1) If consistency ZKPs are standalone or integrated in compliance/logic proofs? (2) How users detect messages are form them and/or how public keys are embedded in the resource object.

Pending things

We could create a separate forum post for this, create issues in the github repository, or just edit this list as new things pop up. Whatever people prefer.

• Need ability to modify/update/delete the set of detection keys associated with each user
• How TEEs communicate to each other or to its (untrusted) outer environment? If the former, TEEs should communicate with each other in a confidential and authenticated manner.
• Are consistency proofs integrated in compliance/logic proofs?
• How are FMD keys embedded in resource objects. Related to: How users identify messages are for them.

[vveiln]

@kike

I didn’t want to deal with it in the first iteration

I think it would be helpful to explicitly say what the limits of the first iteration are and what is the ideal functionality we want to achieve after n iterations. Would also be cool to have a plan for how we get from the simple model to the real model, but that is only possible to an extent, so I’m just dreaming out loud

@kike

I think that at least the last TEE node of the decryption layer should communicate with users directly using a confidential and authenticated channel (If there is only the detection layer, then the last detection TEE.)

I wonder if we can make the whole system stateless so that the tees didn’t have to be aware of each other’s work or existence. I feel like we add a lot of complexity by having it this way. I don’t have an answer to that, but it is something to think about

@kike

Please, feel free to add the request to the pending list below.

I listed it in the last meeting’s notes. We can discuss it more on Thursday, it was more like a future work observation on my side

@kike

Another possibility is to have a separate proof, which may help to optimize the prover.

Can we optimise all RM proofs then, or is it an FMD-proof-specific optimisation? I feel like logically FMD-verifiability belongs where the encryption-verifiability is checked.

@kike

Also, who verifies the consistency ZKPs? the TEEs?

I’m not sure what exactly you mean by consistency ZKPs, but all RM ZKPs are verified the same way: the most important (guaranteed) verifier is the executor. FMD TEEs are not in this scope

@kike

Say m=\mathsf{ShieldRM.Encrypt}((pk_{fmd},\star)), where \star is whatever (plaintext) message the sender is sending to receiver with FMD public key pk_{fmd}

Why would sender use pk_{fmd} to encrypt the payload? But reading further, it seems like this key is not used to encrypt, but is a part of the encrypted data? If that is the case, why is it included?

The statement I had in mind was something like: \vec{f} = FMD.Encrypt(dsk, 1^n), with dsk being private input and \vec{f} being private input.

@kike

The statement also proves mmm is a correct encryption under public key pk_{shield} and randomness r – but I omitted that in the informal description as its is not the essential bit.

This is the verifiable encryption constraint already included in the RM circuits, if I understand you correctly, so we don’t need to include it here

@kike

How do users identify messages are for them after they decrypt m?

That is the idea behind trial decryption, I think: if the user can decrypt a message, it means it was send to them. We already have payload encryption mechanism that solves these problems

[kike]

Hi @vveiln . Thanks for your replies!

@vveiln

I think it would be helpful to explicitly say what the limits of the first iteration are and what is the ideal functionality we want to achieve after n iterations.

I wrote the basic proposal based on this comment:

@cwgoes

Most important aspect of first proposal is a single detection layer that can run FMD in a TEE with the right cryptography and some proof that the clue is correct.

Regarding what we ideally want to achieve, yes that’s something to think about it.

@vveiln

@kike

I think that at least the last TEE node of the decryption layer should communicate with users directly using a confidential and authenticated channel (If there is only the detection layer, then the last detection TEE.)

I wonder if we can make the whole system stateless so that the tees didn’t have to be aware of each other’s work or existence. I feel like we add a lot of complexity by having it this way. I don’t have an answer to that, but it is something to think about

I was answering how users and TEEs communicate. I think we agree on this.

You may be right, but I also think we may benefit by having TEEs working together, specially for privacy.

Re the ZKPs of FMD falg consistency. Sorry it wasn’t very clear, hopefully in this post is clearer.