Parent Hash. ∈ Ratchet trees in TreeKEM contain so-called parent hashes, which were introduced to the standard in TreeKEM v9, and analyzed and improved by Xxxxx et al. [5]. These ensure, on the one hand, that for every node v T, whoever sampled skv had knowledge of the secret signing key for some leaf l of the subtree rooted at v; and on the other, that at the moment this secret was generated it was not communicated to any user whose leaf is not in this subtree. This protects against active attacks where a user is added to a malformed group where the tree invariant is violated, potentially causing him to communicate to a set of users different to the one he believes to be communicating to. To adapt parent hash to CoCoA we have to overcome the two issues that (a), since parties update concurrently, parent hash values can be defined with respect to keys on the copath that were overwritten by a concurrent update, and (b), since the resolution of a user’s copath and in turn the corresponding public keys that are known to the user may change from round to round, the user needs to be able to verify the authenticity of such keys without having access to the state of leaves below it. We address the first issue by having users store the public keys of one previous round: each node state γ(v) now contains an associated list of predecessor keys, PKpr, containing the public keys corresponding to nodes in the resolution of v in the epoch when the current key was sampled, and excluding those that where unmerged at child(v);9 i.e. if the Update sampling pkv unblanked v, the predecessor keys will be a list, else it will just contain the previous public key. The second issue we solve by not only signing the parent hash value of users’ leaves but by introducing a signature at every node in their update path (that which is sent with the packet containing the new public key when it is first announced). Last, to ensure consistency between users’ views, we add two further values to the parent hash and node state: a commitment to the subtree under the node’s sibling and a commitment to the whole ratchet tree. We now define more formally the slightly modified parent-hash algorithm, compatible with our construction, with respect to signature scheme Sig. As in TreeKEM, parent hash values of a node are updated whenever the key corresponding to the node is updated. More in detail, let ID compute an Update U containing new keys for nodes along their path (see full definition in Section 3.5), which...
