Security Analysis of DGM and GM Group Signature Schemes Instantiated with XMSS-T

Group Merkle (GM) (PQCrypto 2018) and Dynamic Group Merkle (DGM) (ESORICS 2019) are recent proposals for post-quantum hash-based group signature schemes. They are designed as generic constructions that employ any stateful Merkle hash-based signature scheme. XMSS-T (PKC 2016, RFC8391) is the latest stateful Markle hash-based signature scheme where (almost) optimal parameters are provided. In this paper, we show that the setup phase of both GM and DGM does not enable drop-in instantiation by XMSS-T which limits both designs in employing earlier XMSS versions with sub-optimal parameters which negatively affects the performance of both schemes. Thus, we provide a tweak to the setup phase of GM and DGM to overcome this limitation and enable the adoption of XMSS-T. Moreover, we analyze the bit security of DGM when instantiated with XMSS-T and show that it is susceptible to multi-target attacks because of the parallel Signing Merkle Trees (SMT) approach. More precisely, when DGM is used to sign \(2^{64}\) messages, its bit security is 44 bits less than that of XMSS-T. Finally, we provide a DGM variant that mitigates multi-target attacks and show that it attains the same bit security as XMSS-T.