TreeKEM Comparison

See Messaging Layer Security (MLS) for descriptions about TreeKEM, and “Multicast Key Agreement, Revisited” about Multicast.

Options

Left-balanced binary tree – position to add new leaf:

Greedy: choose closest (in terms of LCA) blank leaf or append if no blank leaf
Random: uniformly choose a blank leaf including the append position as a pseudo blank leaf
Append: append to the end

Left-balanced binary tree – truncate strategy:

Truncate: truncate the tree when the leaf at the end is removed
Keep: keep the removed leaf at the end as blank leaf
Balance: rearrange the leaves so that the removed leaf switches to the end and can always be truncated

B tree – position to add new leaf:

Greedy: place the new leaf such that it shares the same parent with a reference leaf (the adder in TreeKEM)
Random: follow greedy policy with a uniformly chosen reference leaf

B tree – degree:

3: 2-3 tree
4: 2-3-4 tree

LLRB tree – position to add new leaf:

Greedy: place the new leaf such that it shares the same parent with a reference leaf (the adder in TreeKEM)
Random: follow greedy policy with a uniformly chosen reference leaf

LLRB tree – equivalent degree:

2-3-4: isomorphic to 2-3-4 tree
2-3: isomorphic to 2-3 tree i.e. forbid two red children

TreeKEM-related options are temporarily unavailable.
(See the GitHub repository for a previous version working with TreeKEM, while having no support for Multicast.)

TreeKEM:

To test against TreeKEM

TreeKEM – add strategy:

Async-sync: async for left-balanced binary tree and sync for B tree
Async: exclude update of new user in add, simply blank out the path (update of new user is possibly done asynchronously when the new user gets online for the first time)
Sync: include update of new user (done by adder) in add

TreeKEM – remove strategy:

Remover: blank out the direct path of removee, remove from tree, and then update at the remover
Remover-before: blank out the direct path of removee, update at the remover, and then remove from tree
Removee: update at the removee and then blank out (and then remove from tree)

TreeKEM – update strategy:

LCA: blank out until the lowest common ancestor
Root: blank out whole direct path

TreeKEM – merge strategy:

Blank: blank out merged node
Keep: keep secret that only covers a subset of children at merged node

TreeKEM – split strategy:

Blank: blank out split node
Keep: keep secret that covers the children at grandparent node

Multicast:

To test against Multicast

Experiment – initial group size n: (separate by comma "," to compare multiple values)

Experiment – random operation number k: (separate by comma "," to compare multiple values)

Experiment – add operation weight w_add: (separate by comma "," to compare multiple values)

Experiment – update operation weight w_update: (separate by comma "," to compare multiple values)

w_remove = 1 - w_add - w_update; when the group size is 1 no randomization is performed and add operation is forced

Experiment – insert update at first operation:

Async-sync: insert for add strategy async and untouched for sync
Insert: insert an update operation at each user's first operation
Untouched: keep the operation sequence untouched

Experiment – operation sequence:

Manual sequence: (e.g. `add,0,n,update,n,remove,n,0`)

Experiment – trace trees:

Trace Log:

Randomness:

Uniform: whenever choosing a random user for add/remove/update, choose uniformly
Geometric: whenever choosing a random user for add/remove/update, choose (the index of user) according to (truncated) geometric distribution with parameter p; i.e. the first user with probability p, the second (1 - p) p, etc.
Reversed Geometric: similar to Geometric, counting from the last user

Randomness – parameter p of geometric distribution:

Should have 0 < p < 1 strictly as in remove operations two different users need to be chosen.

TreeKEM Comparison

Options

Results Restart

Results