Paper 2023/1053

ASMesh: Anonymous and Secure Messaging in Mesh Networks Using Stronger, Anonymous Double Ratchet

Alexander Bienstock, New York University
Paul Rösler, FAU Erlangen-Nürnberg
Yi Tang, University of Michigan

The majority of secure messengers have single, centralized service providers that relay ciphertexts between users to enable asynchronous communication. However, in some scenarios such as mass protests in censored networks, relying on a centralized provider is fatal. Mesh messengers attempt to solve this problem by building ad hoc networks in which user clients perform the ciphertext-relaying task. Yet, recent analyses of widely deployed mesh messengers discover severe security weaknesses (Albrecht et al. CT-RSA'21 & USENIX Security'22). To support the design of secure mesh messengers, we provide a new, more complete security model for mesh messaging. Our model captures forward and post-compromise security, as well as forward and post-compromise anonymity, both of which are especially important in this setting. We also identify novel, stronger confidentiality goals that can be achieved due to the special characteristics of mesh networks (e.g., delayed communication, distributed network and adversary). Finally, we develop a new protocol, called ASMesh, that provably satisfies these security goals. For this, we revisit Signal's Double Ratchet and propose non-trivial enhancements. On top of that, we add a mechanism that provides forward and post-compromise anonymity. Thus, our protocol efficiently provides strong confidentiality and anonymity under past and future user corruptions. Most of our results are also applicable to traditional messaging. We prove security of our protocols and evaluate their performance in simulated mesh networks. Finally, we develop a proof of concept implementation.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM CCS 2023
Mesh MessagingDouble RatchetAnonymityASMeshAnonymous MessagingSecure Messaging
Contact author(s)
abienstock @ cs nyu edu
paul roesler @ fau de
yit @ umich edu
2023-09-05: last of 2 revisions
2023-07-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alexander Bienstock and Paul Rösler and Yi Tang},
      title = {ASMesh: Anonymous and Secure Messaging in Mesh Networks Using Stronger, Anonymous Double Ratchet},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1053},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.