Re: [MLS] Re-randomized TreeKEM

[Brendan McMillion <[e-mail]>]

> 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.
>

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:
      - 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:
   - 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.
      - 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.

Yes, RTreeKEM has very good best-case behavior when you know exactly who is
compromised and when. But in reality, RTreeKEM can only be expected to
recover twice as fast in the best-case (6h vs 12h), and is the same in the
worst-case (24h).


> 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.
>

The purpose of an ACK would be to let us know when everyone has processed
the most recent Update message -- that is, when FS has been achieved.
Without an ACK, the fact that RTreeKEM achieves FS faster than TreeKEM is
useless for applying any sort of policy to manage the FS properties of the
group, because nobody knows when FS is achieved.

Although of course, PCS still won't be achieved until everybody Updates. So
everybody Updates, everybody ACKs everybody's Updates, and the number of
messages sent is n^2. That's not scalable so the fact that RTreeKEM
achieves FS faster can't be enforced, which means it can't be relied on.