Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Messaging Layer Security, Group Key-Agreement Protocols, TreeKEM, Adaptive Security

Date: received 27 Dec 2019

Contact author: guillermo pascualperez at ist ac at,michael walter@ist ac at,krzpie@gmail com,jalwen@wickr com,karen klein@ist ac at

Available format(s): PDF | BibTeX Citation

Version: 20191230:193456 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]