Re: [MLS] ART Ideas in TreeKEM

[Richard Barnes <[e-mail]>]

Hi Matthew,

Thanks for the thoughts.  Would it be accurate to summarize your proposal
as a "hybrid mode", where when you update:

- If both of a node's children are populated, then you do an "ART step",
generating the parent from the children
- Otherwise, you do a "TreeKEM step", encrypting the next secret to the
resolution of the other child

(Remove is probably similar; for Add there's no change needed.)

Assuming that's right, this honestly doesn't sound like a tremendously
compelling proposition to me.  Your evaluation on the overhead seems mostly
correct, but there have already been some complaints on the list about
hashing overhead, so I'm not sure trading DH+smaller_messages for hashing
is going to suit.  I'm also worried that this hybridization will introduce
a bunch of new complexity into the protocol and make it harder to implement
and analyze.  Open to arguments if other folks are enthusiastic, though.

--Richard







On Mon, Feb 25, 2019 at 4:37 PM M.A.L. Weidner <[e-mail]> wrote:

> 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
> _______________________________________________
> MLS mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/mls
>