Paper 2022/1531

The Key Lattice Framework for Concurrent Group Messaging

Kelong Cong, imec-COSIC, KU Leuven, Leuven, Belgium
Karim Eldefrawy, SRI International, Menlo Park, U.S.A.
Nigel P. Smart, imec-COSIC, KU Leuven, Leuven, Belgium., Zama Inc, France.
Ben Terner, University of California Irvine, Irvine, U.S.A.

Today, two-party secure messaging is well-understood and widely adopted on the Internet, e.g., Signal and WhatsApp. Multiparty protocols for secure group messaging on the other hand are less mature and many protocols with different tradeoffs exist. Generally, such protocols require parties to first agree on a shared secret group key and then periodically update it while preserving forward secrecy (FS) and post compromise security (PCS). We present a new framework, called a key lattice, for managing keys in concurrent group messaging. Our framework can be seen as a ``key management'' layer that enables concurrent group messaging when secure pairwise channels are available. Proving security of group messaging protocols using the key lattice requires new game-based security definitions for both FS and PCS. Our new definitions are both simpler and more natural than previous ones, as our framework combines both FS and PCS into directional variants of the same abstraction, and additionally avoids dependence on time-based epochs. Additionally, we give a concrete, standalone instantiation of a concurrent group messaging protocol for dynamic groups. Our protocol provides both FS and PCS, supports concurrent updates, and only incurs $O(1)$ overhead for securing the messaging payload, $O(n)$ update cost and $O(n)$ healing costs, which are optimal.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACNS 2023
Contact author(s)
kelong cong @ esat kuleuven be
karim eldefrawy @ sri com
nigel smart @ kuleuven be
bterner @ uci edu
2023-11-07: last of 2 revisions
2022-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kelong Cong and Karim Eldefrawy and Nigel P. Smart and Ben Terner},
      title = {The Key Lattice Framework for Concurrent Group Messaging},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1531},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.