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:

Left-balanced binary tree – truncate strategy:

B tree – position to add new leaf:

B tree – degree:

LLRB tree – position to add new leaf:

LLRB tree – equivalent degree:

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

TreeKEM:

TreeKEM – add strategy:

TreeKEM – remove strategy:

TreeKEM – update strategy:

TreeKEM – merge strategy:

TreeKEM – split strategy:

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:

Experiment – operation sequence:

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

Experiment – trace trees:

Trace Log:

Randomness:

Randomness – parameter p of geometric distribution:

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

Results

Method n k wadd wremove wupdate kadd kremove kupdate #PRG #Gen #Enc #Dec #Dec-PRG #Dec-Gen Op. Seq. Trace