Re: [MLS] Re-randomized TreeKEM

[Joel Alwen <[e-mail]>]

> RTreeKEM might get to a secure state faster but it's not that much faster, and it doesn't change the promises we can make to our users.

I'm curious what leads you to this conclusion. Suppose Alice produces an update defining new group key K. If the
adversary can't already process the update then with RTreeKEM we get FS for K once the update is processed by all
parties. For TreeKEM not only must that hold but we then need a further order n other parties to send out their own
updates too. At least in terms of # of message flows and total bandwidth (and, most likely, in terms of time) that gap
seems pretty big to me.

Moreover, to me this sounds like both a qualitative and quantitative change in the security promise. E.g.
  Quantitative: FS is achieved with fewer message flows & bandwidth.
  Qualitative : FS can be maintained even when there o(n*log(n)) bandwidth. Instead, O(log n) suffices.

> Having everybody send an ACK requires either quadratic bandwidth or trusting the server, which isn't worth it imo.

I dont follow. If I understood your earlier email correctly you said that updates in TreeKEM serve as a signal to others
guiding their update policy. All I was proposing was to use a much more lightweight ACK msg in exactly the same way you
thought updates were being used to guide policy.

Regardless, I don't really understand the problem here. RTreeKEM needs linear updates too for PCS. So people should
still be doing regular updates if they can afford to. That means if I don't see updates from Alice for a long time I'll
eventually want her removed from the group because she's harming the group's PCS. In other words, there's still reason
to do frequent updates which means they still serve as a signal that people are present. The main difference to me is
what we can say about time periods where we can't afford linear number of updates. For those cases RTreeKEM can still
give us FS but not TreeKEM.

- Joël