[MLS] Re: On the Efficiency of MLS

[Richard Barnes <[e-mail]>]

Hi Miguel, (and Ben and Boran and Krzysztof)

Thanks for sharing this work.  Your point about "fair-weather" complexity
matches what I expect is the intuition of most folks who have worked with
MLS a bunch.  For example, in our Real-World Crypto talk on MLS in 2019
[1], we talked about Update and Remove operations costing log(N) ~ N to
give a sense of this spectrum. (As for the RFC text you quote... maybe that
was a bit optimistic :) ) But it's still nice that this work adds some
precision to that intuition.

--Richard

[1] https://www.youtube.com/watch?v=9xePC0Tyeuc&t=1810s

On Thu, Nov 20, 2025 at 11:06 AM Miguel Cueto Noval <
[e-mail]> wrote:

> Dear all,
>
> I am a PhD student at ISTA working in cryptography. At CRYPTO 25, Benedikt
> Auerbach, Boran Erol and Krzysztof Pietrzak and I presented our work on the
> efficiency of MLS 'Continuous Group-Key Agreement: Concurrent Updates
> without Pruning'.
>
> In this paper (https://eprint.iacr.org/2025/1035) we study the
> Propose-and-Commit paradigm used in TreeKEM and the impact it has on the
> efficiency of the protocol, in particular the “update complexity” measured
> by the number of ciphertexts that the committer must upload (per updated
> party) as part of a commit.
>
> Depending on the number and distribution of proposals/commits, for
> MLS/TreeKEM this complexity lies somewhere between log(N) and N (where N is
> the number of parties). While we couldn’t find any concrete analysis or
> claims about the exact complexity, some works suggested that under mild
> assumptions about the online/offline behaviour of participants, the
> complexity can be kept in the O(log(n)) range (aka. “Fair-weather”
> complexity). The IETF document states “This mechanism allows the members of
> the group to derive and update shared keys with costs that scale as the log
> of the group size.”.
>
> In our work we show that this intuition is wrong. Already for the simple
> and seemingly nice (i.e., “fair-weather”) case where we alternatingly pick
> a random proposer and then a random committer, the complexity is around
> N^(0.5), and the complexity converges fast towards N as the number of
> proposers increase.
>
> On the positive side, we construct a new variant of Propose-and-Commit for
> TreeKEM which for moderate amounts of update proposals per commit provably
> achieves an update cost of $\Theta(\log(N))$. Moreover, the changes
> required for this variant are relatively small meaning that an
> implementation of MLS should be easily adapted to make use of this variant.
>
> Best,
> Ben, Boran, Krzysztof and Miguel
>
> _______________________________________________
> MLS mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>