Re: [MLS] Re-randomized TreeKEM

[Joel Alwen <[e-mail]>]

Hey Brendan,

Thanks for taking the time to look at this stuff and answer! :-)

> This actually makes TreeKEM more attractive to me because it encourages
> implementors to keep the Update frequency high, 

If one can afford high update frequency then that's great. It helps
RTreeKEM too by the way. The longer between updates the less PCS we have
and the longer the corruption windows. So there's still plenty of
incentive in RTreeKEM to update as often as you can.

But more generally, to me a primary design goal for MLS is to get as
much security for as little bandwidth as possible. So I'm particularly
interested in the protocols behavior when there *isn't* that much
bandwidth to spare for frequent updates.

> and it provides an
> explicit signal to the group that everyone has processed every update.
> With TreeKEM, the policy would be “everybody Updates at least once per
> day”. But with RTreeKEM, the equivalent policy is “at least one person
> Updates every day” which isn’t as strong, because you don’t know whether
> or not everybody came online that day and processed the one Update.

If your not coming online then I'm not sure I see the difference between
using TreeKEM or RTreeKEM. I mean, either way your not refreshing any
key material so your preventing the group from achieving FS. Moreover,
coming online to send a daily update TreeKEM means already requires
processing other peoples updates first.

If, on the other hand, the concern is the lack of an explicit signal
wouldnt it be enough to have parties send out ACK msgs to the group when
they process an update? That would consume far less bandwidth (and
computation) than doing a full update alla TreeKEM.

> But RTreeKEM has costs like being harder to implement, and restricting what
> algorithms we can use.

FYI: In the mean time it looks like we may have found a way to make
RTreeKEM work with X25519/X448 groups. (See the email I just sent to the
group for more on this.) Harder to implement I do agree with. Albeit IMO
the difference is rather marginal compared to how much code is needed to
implement the rest of MLS, not to mention all the surrounding
infrastructure; e.g. the servers, the rest of the client, UX etc need to
actually deploy MLS. At the end of the day, I don't think we're talking
about much more than a few lines of code wrapping HPKE. But I might be
wrong here.

> It’s on this basis that I’m opposed to including RTreeKEM in the spec.

Fair enough! :-)

- Joël