Paper 2019/1489

Keep the Dirt: Tainted TreeKEM, an Efficient and Provably Secure Continuous Group Key Agreement Protocol

Joel Alwen and Margarita Capretto and Miguel Cueto and Chethan Kamath and Karen Klein and Guillermo Pascual-Perez and Krzysztof Pietrzak and Michael Walter

Abstract

While end-to-end encryption protocols with strong security are known and widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains an open problem. The only known approaches to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). ART enjoys a security proof, albeit with a superexponential bound, and is not dynamic enough for practical purposes. TreeKEM has not been proven secure at this point and can suffer some efficiency issues due to dynamic group operations (i.e. adding and removing users). As a first contribution we present a variant of TreeKEM, that we call Tainted TreeKEM, which can be more efficient than TreeKEM depending on the distribution of add and remove operations. Our second contribution is a security proof for Tainted TreeKEM (and also TreeKEM) with a meaningful security bound against active and adaptive adversaries, showing that the protocol supports post compromise security and forward security. Concretely, we achieve an only slightly superpolynomial security loss of q^{\log\log(n)}, where n is the group size and q the total number of (update/remove/invite) operations.