Re: [MLS] TreeKEM: An alternative to ART

[Eric Rescorla <[e-mail]>]

Oops. I forgot to attach the paper.


On Thu, May 3, 2018 at 7:26 AM, Eric Rescorla <[e-mail]> wrote:

> Hi folks,
>
> Several of us (Karthik, Richard, and I) have been working on an
> alternative to ART which we call TreeKEM. TreeKEM parallels ART in
> many ways, but is more cryptographically efficient and is much better
> at handling concurrent changes. The most common behaviors (updating
> ones own key) can be executed completely concurrently, merging all the
> requested changes.
>
> We've attached a draft technical paper describing the details, and
> some slides, but here's a brief overview of TreeKEM.
>
> Code: https://github.com/bifurcation/treekem, https://github.com/
> bifurcation/treekem
> Explainer slides: https://docs.google.com/presentation/d/
> 1myiQ22ddxHAcF8uCJBXk9cdJMvAQfAw9nmKiqE5seJc/edit?usp=sharing
>
> As with ART, TreeKEM addresses the scaling problem by arranging nodes
> in a binary tree. In the steady state, each node i has a key pair but
> instead of having two siblings do DH to determine their shared key, we
> derive the shared key by hashing the key of the last node to update.
> As before, each node knows all the keys to its parents.
>
> Imagine we have the four node tree a, b, c, d which was constructed
> in that order. The private keys at each vertex are shown below.
>
>        H^2(d)
>       /     \
>     H(b)    H(d)
>     / \     / \
>    a   b   c   d
>
>
> UPDATES
> Now say that b wants to update its key to b', giving us the tree:
>
>        H^2(b')
>       /     \
>     H(b')   H(d)
>     / \     / \
>    a   b'  c   d
>
> This requires providing
>
>   - a with H(b') -- note that a can compute H^2(b') for itself.
>   - c and d with H^2(b')
>
> Recall that you can encrypt to any subset of the tree by just
> encrypting to the appropriate set of parent nodes. So, we can
> do this by sending:
>
>   - E(pubkey(a), H(b'))
>   - E(pubkey(H^2(d)), H^2(b'))
>
> Where pubkey(k) gives the public key derived from private key k.
>
> As with ART, you then mix the new tree root (H^2(b')) into the current
> operational keys and use the result to derive the actual working keys.
>
>
> CONCURRENT UPDATES
> The big win in TreeKEM is that you can handle an arbitrary number
> of concurrent updates, just by applying them in order. Again,
> consider our starting tree, but assume that b and c both try to
> update at once. a thus receives two updates
>
>   - E(pubkey(a), H(b'))       [b's update]
>   - E(pubkey(H(b)), H^2(c'))  [c's update]
>
> If we apply these in order b, c we get the tree:
>
>        H^2(c')
>       /     \
>     H(b')   H(c')
>     / \     / \
>    a   b'  c   d
>
> a can easily compute this.
>
> In order to make this work, we need two things:
>
> 1. a needs to keep a copy of its current tree around until it has
>    received all updates based on that tree
> 2. there needs to be an unambiguous ordering of updates
>
> The way to handle (1) is probably to have some defined "window"
> of time during which an update can be received. The node needs
> to hold onto its old key until that window has passed. (2) can
> be handled by having the messaging system provide a consistent
> order and then agreeing to apply updates consecutively. If we
> want to concurrently apply other changes, we may need to sort
> based on change type within the window.
>
>
> ADDS
> In order to add itself to the group (USERADD), a node merely puts
> itself at the right position in the tree and, generates a random key,
> and then sends the appropriate keying material to everyone in its path
> to the root.
>
> In order to add another node to the group (GROUPADD), the adding
> node does exactly the same thing as with a USERADD, but also sends
> a copy of the new key to the node being added. Note that this creates
> a double-join, which we will cover later.
>
>
> REMOVAL
> In order to remove another node from the tree, the removing node
> sends the same message that the evicted node would have sent if
> it had sent an update, but with a new key not known to the evicted
> node (note that this naturally omits the evicted node, because you
> encrypt to the co-path). This also creates a double-join, where the
> removing node knows the dummy key.
>
>
>
> STATE
> In order to receive messages, a node need only keep its secret keys,
> which range between 1 key (if it was the last to update) and log(N)
> keys (in the worst case).
>
> In the best case, in order to update, a node needs to also know
> the public keys for everyone on its co-path. However.
>
> In order to be able to do deletes, a node also needs to be able
> to get the public key for any node in the tree (leaf or internal).
> It's easy to see this by realizing that to delete a node you need
> to encrypt a new key to its sibling, and so to delete any node,
> you need to be able to access every node's public key. However,
> a node need not store this information, but can retrieve it
> on demand when it needs to delete another node.
>
>
> EFFICIENCY
> The paper contains more details. but generally TreeKEM is somewhat
> more efficient in terms of asymmetric crypto operations than ART.
>
>
> DOUBLE JOINS
> Like ART, TreeKEM has double-join problems whenever one group member
> provides a service (or a disservice, in the case of remove) for another
> group member. In the case of GROUPADD, the double join will resolve itself
> as soon as the added node updates its key. However in the case of
> REMOVE, this cannot happen, and so double join needs to be
> dealt with in some other way.
>
> One option is to have selective updates: each node keeps track of
> extra tree state and uses it to control its updates. For instance,
> if we never send updates to deleted nodes, than as soon as a deleted
> node's sibling sends an update, the double-join will be resolved.
> In a more sophisticated -- but also more expensive to implement --
> version, we track which nodes control the keys of other nodes and
> REMOVE all affected nodes when we do a delete.
>
> -Ekr
>
>