Re: [MLS] Re-randomized TreeKEM

[Konrad Kohbrok <[e-mail]>]

> Let's work an example. Say we set a policy that everyone should try to Update
> every 12h and those that don't will be removed after 24h. One user is
> compromised. How long is it until full FS and PCS is restored?
> 
>   * If the user is prevented from sending new Updates:
>       o Whether you use TreeKEM or RTreeKEM, the group is secure again after the
>         user is removed. So after 24h at most, but 12h on average if the user is
>         compromised at a random time.
>   * If the user is not prevented from sending new Updates:
>       o With TreeKEM, you must wait until everyone sends an Update. We're secure
>         again after 24h at most, per policy. The average would trend toward 12h
>         if everybody's Updates are uniformly distributed.
>       o With RTreeKEM, you must wait until the compromised user sends an Update.
>         The user could be compromised immediately after sending an Update, so
>         we're secure again after 12h max. On average, you could say that it's
>         more like 6h.
> 

You're right in this particular example (although I think that eviction after
24h is pretty draconic). However, if you're looking at larger groups (>10.000
members) you might want to scale down the update frequency to avoid everyone
having to process 10.000 updates of a 10.000-member group every 12h. I'm not an
implementer, but I could imagine that this is pretty costly on battery powered
devices (please feel free to correct me if I'm wrong). In those cases, getting
FS for everyone just by processing a single update of any member is pretty
significant. I guess my expectation is that in large groups, other constraints
that also exist with "simple" TreeKEM will dictate a lower update frequency and
thus PCS guarantees will be rather weak, but that doesn't mean that FS
guarantees have to be.

Also keep in mind that even if it's not very beneficial in the example, we
generally get substantially better FS guarantees at a relatively small price in
bandwidth and local computation. Throwing that away because the upside is not
very big in some cases seems unnecessary to me.

If I understand you correctly, then your concern is that implementers could
think that due to the guarantees provided by RTreeKEM, they can get away with a
lower update frequency while maintaining the same security guarantees. That
seems to be a problem that can be solved by providing clear information on what
guarantees are provided upon an update and/or emphasizing the difference between
FS and PCS.

Cheers,
Konrad