Paper 2024/014

A Lattice-based Accountable Subgroup Multi-signature Scheme with Verifiable Group Setup

Abstract

An accountable subgroup multi-signature (ASM) is a multi-signature that allows any subgroup of potential signers to jointly sign a message such that the subgroup of co-signers are accountable for the resulting signature and their identities are identifiable to any verifier. In this paper, we pro- pose a novel lattice-based accountable subgroup multi-signature scheme, i.e., vMS2, by combining the group setup method of recently proposed vASM scheme and Damgard et al.’s lattice-based MS2 multi-signature scheme. Key generation, signature generation and verification phases of our proposed scheme are almost identical to the MS2 scheme. In the group setup phase, we generate membership keys which is used for signing a message on behalf of a group G of users. These membership keys are generated via a joint verifiable secret sharing (VSS) scheme in a way that they include a piece of information from the secret keys of all users in G so that any subgroup of users in G having a valid membership key can sign in an accountable fashion. We also present a comparison of the underlying MS2 scheme and our accountable subgroup multi-signature scheme vMS2 to show the cost of accountability. We see that lattice-based accountable subgroup multi-signature scheme can be achieved by adding a one-time one-round group setup whose cost is slightly higher than signature generation and verification of the underlying MS2 signature scheme.