A Framework for Group Action-Based Multi-signatures and Applications to LESS, MEDS, and ALTEQ

A multi-signature scheme allows a list of signers to sign a common message. They are widely used in scenarios where the same message must be signed and transmitted by. N users, and, instead of concatenating. N individual signatures, employing a multi-signature can reduce the data to be sent. In recent years there have been numerous practical proposals in the discrete logarithm setting, such as MuSig2 (CRYPTO’21) for the Schnorr signature. Recently, these attempts have been extended to post-quantum assumptions, with lattice-based propos als such as MuSig-L (CRYPTO’22). Given the growth of group action based signatures, a natural question is whether a multi-signature can be built on the same models. In this work, we present the first construction of such a primitive relying on group action assumptions. We obtain a 3 round scheme achieving concurrent security in the ROM. Moreover, we instantiate it using the three candidates to the additional post-quantum NIST’s call, namely LESS, MEDS and ALTEQ, obtaining a good com pression rate for different parameters sets.