Labeled Trees. The primary object making up the construction’s (distributed) state γ is a labeled left-balanced binary tree (LT) τ . We distinguish between the public part of τ which does not need to be hidden from the adversary and the private part of τ , i.e., those labels corresponding to secret values. In particular, private labels will (usually) only be known to a particular subset of the group. So, while the tree structure (i.e. the set of nodes and edges) as well as labels holding public keys are all public and known to all group members, other labels holding the matching secret keys are private. A group member’s view of the LT consists of both the public and their private part of LT. Recall that the sessions evolve in epochs which are initiated by processing an incoming commit message. Each epoch has a fixed LT. Proposals represent suggestions for modifying the current LT (e.g. by adding or removing nodes and/or modifying labels). To produce a commit message the committer gathers such proposals, applies the changes to the current LT resulting in a new LT. Next, they compute and distribute a message to all other group members allowing them to compute their respective views of the new LT. Labels. In more detail, an LT is an LBBT on n nodes (for some value n which changes as the group evolves). The value of n (and thus the entire tree structure of LT) is public. Each node v in LT has 3 public mpk, i˙d and taintedby as well as 1 private label hsk. In the order listed, the public labels contain a HIBE master public key, a HIBE ID (vector) and the ID of the party which “tainted” (i.e. sampled) mpk. Finally, hsk contains a HIBE secret key the ID i˙d under master public key mpk. Besides the node labels an LT has a private label grpkey which holds the value of the group key for the current epoch.
