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 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 < 1
strictly as in remove operations two different users need to be chosen.