Paper 2021/1497

GMMT: A Revocable Group Merkle Multi-Tree Signature Scheme

Mahmoud Yehia, Riham AlTawy, and T. Aaron Gulliver


G-Merkle (GM) (PQCrypto 2018) is the first hash-based group signature scheme where it was stated that multi-tree approaches are not applicable, thus limiting the maximum number of supported signatures to $2^{20}$. DGM (ESORICS 2019) is a dynamic and revocable GM-based group signature scheme that utilizes a computationally expensive puncturable encryption for revocation and requires interaction between verfiers and the group manager for signature verification. In this paper, we propose GMMT, a hash-based group signature scheme that provides solutions to the aforementioned challenges of the two schemes. GMMT builds on GM and adopts a multi-tree construction that constructs new GM trees for new signing leaves assignment while keeping the group public key unchanged. Compared to a single GM instance which enables $2^{20}$ signature, GMMT allows growing the multi-tree structure adaptively to support $2^{64}$ signatures under the same public key. Moreover, GMMT has a revocation mechanism that attains linkable anonymity of revoked signatures and has a logarithmic verfication computational complexity compared to the linear complexity of DGM. The group manager in GMMT requires storage that is linear in the number of members while the corresponding storage in DGM is linear in the number of signatures supported by the system. Concretely, for a system that supports $2^{64}$ signatures with $2^{15}$ members and provides 256-bit security, the required storage of the group manager is 1 MB (resp. $10^{8.7}$ TB) in GMMT(resp. DGM).

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. CANS 2021
Hash-based group signatures
Contact author(s)
raltawy @ uvic ca
2021-11-15: received
Short URL
Creative Commons Attribution


      author = {Mahmoud Yehia and Riham AlTawy and T.  Aaron Gulliver},
      title = {GMMT: A Revocable Group Merkle Multi-Tree Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1497},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.