International Association
for Cryptologic Research

Continuous Group Key Agreement (CGKA) is the primitive underlying group messaging. It allows group members to issue updates, by which they rotate their key material in order to achieve forward secrecy and post compromise security. The MLS IETF working group proposed TreeKEM as a CGKA. It arranges the N users in a binary tree, where each node is associated with a public-key, and a user knowns the corresponding secret keys from their leaf to the root. To update, a user must just replace keys at \log(N) nodes, which requires them to create and upload \log(N) ciphertexts. Such updates must be processed sequentially by all users, which for large groups is impractical. To allow for concurrent updates, TreeKEM uses the ``propose and commit'' approach, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit all proposals at once. Unfortunately this process destroys the binary tree structure as the tree gets pruned and some nodes must be ``blanked'' at the cost of increasing the in-degree of others, which can make future updates more costly. In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from \log(N) to \Omega(N). Our first contribution is to show that the efficiency is terrible already if the proposers and committers are chosen at random (and not worst case): even if there's just one commit for every proposal the cost is already over \sqrt{N}, and it approaches $N$ as this ratio changes towards more proposals. Our main contribution is a new variant of propose and commit for TreeKEM which provably achieves an update cost of \Theta(\log(N)) assuming the proposers and committers are chosen at random. To achieve this we put a slightly higher cost on the proposers, which now upload \log(N) ciphertexts. This allows the committer to keep the tree mostly intact as pruning mostly happens at the very top layers.