Paper 2019/1489

Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement

Joël Alwen, Margarita Capretto, Miguel Cueto, Chethan Kamath, Karen Klein, Ilia Markov, Guillermo Pascual-Perez, Krzysztof Pietrzak, Michael Walter, and Michelle Yeo


While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations. Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. If $n$ is the group size and $Q$ the number of operations, the security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor $(Qn)^2$, and in the Standard Model a quasipolynomial $Q^{\log(n)}$. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security - where also the users can arbitrarily deviate - remains open.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. IEEE Symposium on Security and Privacy 2021
Messaging Layer SecurityGroup Key-Agreement ProtocolsTreeKEMAdaptive Security
Contact author(s)
guillermo pascualperez @ ist ac at
michael walter @ ist ac at
krzpie @ gmail com
jalwen @ wickr com
karen klein @ ist ac at
2020-10-20: last of 2 revisions
2019-12-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joël Alwen and Margarita Capretto and Miguel Cueto and Chethan Kamath and Karen Klein and Ilia Markov and Guillermo Pascual-Perez and Krzysztof Pietrzak and Michael Walter and Michelle Yeo},
      title = {Keep the Dirt: Tainted {TreeKEM}, Adaptively and Actively Secure Continuous Group Key Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1489},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.