Re: [MLS] Proposals for handling concurrent messages

[Jeff Burdges <[e-mail]>]

Hello,

Aside form Matrix, there are several groups from the wider Ethereum 2.0 community interested in a messaging scheme that is both distributed and privacy preserving, including both at a cryptographic level and at the metadata level (mix networks).  These include Nym (Panoramix), Status IM, Validity Labs, and the Web 3 Foundation and Parity.

We’re largely out-of-the-loop on MLS but we’re exited about MLS possibly providing a cryptographic layer without too many centralising assumptions.  We’re definitely interested in the “concurrent" updates problem in particular because mix networks can incur considerable latency.

There are also a few projects like Meshenger who should consider using MLS or similar for group messaging over mesh networks.  These have a similar need for concurrent updates, albeit stemming from network topology rather than latency.


Again apologies for my being out-of-the-loop, but I’m not completely sure what concurrency means here.  There is a merge operation that requires any decrypting party processed all the merged trees, yes?  If I understand, there is a similar tree merge operation for vanilla TreeKEM that provides similar assurances to the merge operation that I assume Casual TreeKEM exists to provide:  You simply encrypt the key update messages to anyone who possesses a set of old keys.  This is not actually heavier than encrypting to parties who possess only one key, except that you must identify the set of old keys.

Ignoring the ECC issues [2], there are afaik no commonly discussed post-quantum schemes that support the key combining operation used by Casual TreeKEM, so if Casual TreeKEM is desired then you need an explicit tree merge function too?

All that said, I kinda like that Casual TreeKEM merges seem commutative, but maybe vanilla TreeKEM could support anything useful here by keeping some symmetric key material in a large abelian group?  I’m not sure if I understand the protocol well enough yet to say if that makes sense.

Best,
Jeff

[1]  I spoke with Benjamin some about the header encryption in MLS, which he convinced me looks suitable for some mix network specific concerns.

[2]  There is nothing wrong with requiring Edwards curve arithmetic instead of X25519/X448 of course, but I’m unsure if many constant-time implementations exist besides the Rust curve25519-dalek crate.  I think Ed25519 libraries normally only implement variable-time multiscalar multiplication and constant-time scalar multiplication by the basepoint.  I’d naively assume Weierstrass curves should be avoided due to similar constant-time concerns, but not personally familiar with the implementations.