TreeKEM Comparison
See Messaging Layer Security (MLS) for descriptions about TreeKEM.
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
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.
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 wadd: (separate by comma "," to compare multiple values)
Experiment - update operation weight wupdate: (separate by comma "," to compare multiple values)
wremove = 1 -wadd -wupdate; 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 probabilityp, 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 < 1strictly as in remove operations two different users need to be chosen.