[MLS] ART Ideas in TreeKEM

["M.A.L. Weidner" <[e-mail]>]

Greatings MLS Working Group!

I have been studying the proposals for TreeKEM, and earlier, ART, and noticed a way to use ART's DH tree ideas in TreeKEM, without sacrificing the ability to merge updates or use blank nodes.  My apologies if this has been discussed before or if there are any mistakes.

My main motivation here is to reduce the size of update messages, since the key encrypted keys in addition to new public keys means that they are ~2x as large in TreeKEM as in ART.

Basically, we use TreeKEM, but with ART's key derivation "as" H(X).  That is, when a node C1 gets the new secret X, instead of H(X), its parent gets the new secret

H2(DH(X, priv(C2))) = H2(pub(C2) ^ X) = H2(pub(X) ^ priv(C2))

where C2 is the neighbor of C1, for some hash function H2.  Since TreeKEM is agnostic about H, we can "define"

H(X) := H2(DH(X, priv(C2)))

in this way without issue, noting that the only users who will have to compute H2(DH(X, priv(C2))) are descendants of C1 (who know X) or C2 (who know priv(C2)).

We can merge updates as with "pure" TreeKEM, choosing one update to dominate at nodes where they conflict.  This will cause the tree to cease being a DH tree, which is fine.  Note that descendants of C2 will have to keep around priv(C2) for a short time after it is overwritten in case of simultaneous updates (so that they can compute the parent secret), but that is true for TreeKEM anyway, since any simultaneous update will send data encrypted under pub(C2).

Blank nodes can be handled by reverting to pure TreeKEM: if a node with new secret X has a blank neighbor, set the parent's secret to H(X) and send that separately to every public key in the resolution.

Now instead of including

pub(X), Enc(pub(C2), H(X))

in the RatchetNode struct for node C2, we need merely include pub(X), saving bandwidth.

Pros:
  - reduces the update message size by about 50% in the typical case (I think).
  - we can build a ternary tree using 3-party Joux DH (as with ART), giving a further log_3(2) ~ 0.63 scaling on update message size.  (I think it's possible to do this with pure TreeKEM as well, by replacing the ephemeral DH exchange with a Joux DH when doing asymmetric encryption.)

Cons:
  - forced to use a DH style cryptosystem (bad for post-quantum?) (as with ART).
  - need log(N) DH operations to compute the new key, instead of log(N) hashes (as with ART).  So this is a bad deal if CPU cycles are more expensive than bandwidth.
  - can also reduce bandwidth by 2 just by ratcheting half as often.

I hope you may find this interesting.

Best,
Matthew Weidner
MPhil student, University of Cambridge