Paper 2022/1533

How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum

Keitaro Hashimoto, Tokyo Institute of Technology, National Institute of Advanced Industrial Science and Technology
Shuichi Katsumata, National Institute of Advanced Industrial Science and Technology, PQShield Ltd.
Thomas Prest, PQShield SAS

Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group members), since their knowledge is often needed by the server in order to ensure the proper function of the SGM protocol. In this work, we provide a simple and generic wrapper protocol that upgrades non-metadata-hiding CGKAs into metadata-hiding CGKAs. Our key insight is to leverage the existence of a unique continuously evolving group secret key shared among the group members. We use this key to perform a group membership authentication protocol that convinces the server in an \textit{anonymous} manner that a user is a legitimate group member. Our technique only uses a standard signature scheme, and thus, the wrapper protocol can be instantiated from a wide range of assumptions, including post-quantum ones. It is also very efficient, as it increases the bandwidth cost of the underlying CGKA operations by at most a factor of two. To formally prove the security of our protocol, we use the universal composability (UC) framework and model a new ideal functionality ${\mathcal{F}_{\text{CGKA}}^{\sf mh}}$ capturing the correctness and security guarantee of metadata-hiding CGKA. To capture the above intuition of a ``wrapper'' protocol, we also define a restricted ideal functionality $\mathcal{F}_{\text{CGKA}}^{\sf ctxt}$, which roughly captures a non-metadata-hiding CGKA. We then show that our wrapper protocol UC-realizes ${\mathcal{F}_{\text{CGKA}}^{\sf mh}}$ in the $\mathcal{F}_{\text{CGKA}}^{\sf ctxt}$-hybrid model, which in particular formalizes the intuition that any non-metadata-hiding CGKA can be modularly bootstrapped into metadata-hiding CGKA.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
secure group messaging metadata-hiding messaging layer securitycontinuous group key agreement post-quantum security
Contact author(s)
keitaro hashimoto000 @ gmail com
shuichi katsumata000 @ gmail com
thomas prest @ pqshield com
2022-11-07: approved
2022-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Keitaro Hashimoto and Shuichi Katsumata and Thomas Prest},
      title = {How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1533},
      year = {2022},
      doi = {10.1145/3548606.3560679},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.