Re: [MLS] Simplifying the key schedule

[Benjamin Beurdouche <[e-mail]>]

Hi Joel,

> On Feb 24, 2019, at 6:17 AM, Joel Alwen <[e-mail]> wrote:
> 
> Hi Richard,
> 
> Sandro Corretti and I just discussed the questions you brought up in
> your email about the key schedule and we've come round to the opinion
> that of the options you present we prefer:
> 
> - for the roster a merkle tree seems to be a good solution
> - for the ratchet tree an ampelmann hashing scheme should work well
> 
> In our opinion linear state size (with reasonably small constants) is
> the lesser of the three evils when compared to needing extensive hashing
> for each tree update and needing larger packet sizes for the protocol
> (e.g. due to membership proofs).
> 
> Having said that I wanted to suggest an alternative. Namely, including
> the ID's of leaves as part of what gets hashed for the ratchet tree.
> This makes including the roster redundant which means we would save on
> all the merkle tree storage as well as the hashing during join/leave
> ops. The only cost I see is that we might want to include the *hash* of
> ID's as part of the state to avoid having to recompute when that party
> updates their PK. (But that still needs less storage than a full merkle
> tree on the roster so its also an improvement.)

I am not sure to understand what you mean here :)  while it might be poorly
documented all the user init keys in TreeKEM are already mixed in the
epoch secret because the Group AKE mandates to agree on whom is in
the group at all times. Our issue is that a newcomer cannot use that
information to explicitly check the identities.

In general, I agree that the TreeKEM section of the draft lacks clarity on
what it provides, and I believe it will be helpful to improve upon it so
I will take a pass on it with Karthik before the interim.

Cheers,
B.

> While we are on the subject of amplemann tree's I wanted to make a
> suggestion for how to deal with blank nodes. I think its conceptually
> simpler (and thus hopefully also less error prone / easier to code) then
> using the resolution of blank nodes to define their values in the
> ampelmann hash. We let the value of each node begin with an indicator
> bit b (or octet if thats more practical). So node values are strings of
> the form b || PK. (Alternatively for leaves it would be b || PK ||
> H(ID).) When b indicates the node is blank (b=1) we simply define PK
> (and H(ID)) to be all 0s.
> 
> I'm also in favour of Raphael's suggestion to define the hash of a node
> to be H(L || R || V) where L and R are the hash of the left and right
> child while V denotes the value of the current node. It seems simpler
> than H(H(L || R) || V).
> 
> - Joel