Re: [MLS] Proposals for handling concurrent messages

["M.A.L. Weidner" <[e-mail]>]

From the above discussion, it appears there are a few ideas for how to handle concurrent updates.  Here is my attempt at a summary.

The scenario is that we are sending an update message, and as part of this, we need to send a secret to a node on our copath; this node has k distinct "candidate" public keys, coming from >= k concurrent updates.  Our options are:

1. (Vanilla TreeKEM) Choose one of the candidates arbitrarily and send the secret encrypted under that.
- Cost (compared to an ordinary sequential update): none.
- PCS guarantee (of the secret we send): healed against compromise of the user who contributed the chosen public key.

2. (similar to Causal TreeKEM) "Combine" all of the candidate public keys and send the secret encrypted under that, so that only someone with all of their private keys can decrypt the secret.
- Cost: need to use a cryptosystem that supports key combining (e.g., Ristretto curves).
- PCS guarantee: healed against compromise of any *one* user who contributed a public key.

3. (Vanilla TreeKEM, multiple keys) Encrypt the secret under each of the candidate public keys in sequence, so that only someone with all of their private keys can decrypt the secret.  (I think this is what Jeff was suggesting - correct me if I'm wrong.)
- Cost: k encryptions for me, k decryptions for recipients (instead of 1 in the ordinary case).
- PCS guarantee: healed against compromise of any *one* user who contributed a public key.

4. (Blank out conflicts) Replace conflicted nodes with blanks (including the node we are sending to, and any conflicted children).  Thus we send the secret separately for each of the k candidates, using public keys deep enough in the tree that none of the contributors' old states can decrypt the secret.  In the extreme case where the k public key contributors are the only descendants of the conflicted node, this means we send the secret separately to each contributor.
- Cost: k encryptions for me, k times as much bandwidth.
- PCS guarantee: healed against compromise of any subset of the users who contributed public keys.

Another consideration is how to encrypt ordinary (e.g. chat) messages after concurrent updates lead to multiple choices for the root key.  We get the same guarantee as option 2 if we combine each concurrent updates' contribution into the root key, as in the original TreeKEM proposal or in Causal TreeKEM.  (This can be done using any KDF, since the root key is just a shared secret, not an asymmetric key pair.)  Getting the strong guarantee in option 4 seems harder.  We could adopt a rule that after concurrent updates, users must first send an update before sending ordinary messages, but that could lead to repeated rounds of concurrent updates.

Best,
Matthew Weidner