Cryptology ePrint Archive: Report 2017/666

On Ends-to-Ends Encryption: Asynchronous Group Messaging with Strong Security Guarantees

Katriel Cohn-Gordon and Cas Cremers and Luke Garratt and Jon Millican and Kevin Milner

Abstract: In the past few years secure messaging has become mainstream, with over a billion active users of end-to-end encryption protocols through apps such as WhatsApp, Signal, Facebook Messenger, Google Allo, Wire and many more. While these users' two-party communications now enjoy very strong security guarantees, it turns out that many of these apps provide, without notifying the users, a weaker property for group messaging: an adversary who compromises a single group member can intercept communications indefinitely.

One reason for this discrepancy in security guarantees is that most existing group messaging protocols are fundamentally synchronous, and thus cannot be used in the asynchronous world of mobile communications. In this paper we show that this is not necessary, presenting a design for a tree-based group key exchange protocol in which no two parties ever need to be online at the same time, which we call Asynchronous Ratcheting Tree (ART). ART achieves strong security guarantees, in particular including post-compromise security.

We give a computational security proof for ART's core design as well as a proof-of-concept implementation, showing that ART scales efficiently even to large groups. Our results show that strong security guarantees for group messaging are achievable even in the modern, asynchronous setting, without resorting to using inefficient point-to-point communications for large groups. By building on standard and well-studied constructions, our hope is that many existing solutions can be applied while still respecting the practical constraints of mobile devices.

Category / Keywords: cryptographic protocols /

Date: received 5 Jul 2017, last revised 2 Mar 2020

Contact author: cas cremers at gmail com

Available format(s): PDF | BibTeX Citation

Note: Updated to v2.3. Changelog in Appendix.

Version: 20200302:221723 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]