**Grafting Key Trees: Efficient Key Management for Overlapping Groups**

*Joël Alwen and Benedikt Auerbach and Mirza Ahad Baig and Miguel Cueto and Karen Klein and Guillermo Pascual-Perez and Krzysztof Pietrzak and Michael Walter*

**Abstract: **Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM.

A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users' secret keys while the root is the shared group key. For a group of size $N$, each user just holds $\log(N)$ keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting $2\log(N)$ ciphertexts (encrypting each fresh key on the path under the keys of its parents).

In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group.

We show that in an asymptotic setting (where the number $m$ of groups is fixed while the number $N$ of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution.

As our asymptotic ``solution" converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a ``lattice graph", which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code.

To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.

**Category / Keywords: **group messaging, continuous group-key agreement, multicast, lower bounds

**Original Publication**** (with minor differences): **IACR-TCC-2021

**Date: **received 10 Sep 2021

**Contact author: **alwenjo at amazon com, bauerbac at ist ac at, mbaig at ist ac at, miguel cuetonoval at ist ac at, karen h klein at protonmail com, gpascual at ist ac at, pietrzak at ist ac at, michael walter at zama ai

**Available format(s): **PDF | BibTeX Citation

**Version: **20210914:175015 (All versions of this report)

**Short URL: **ia.cr/2021/1158

[ Cryptology ePrint archive ]