Paper 2022/018

Pairing-based Accountable Subgroup Multi-signatures with Verifiable Group Setup

Ahmet Ramazan Ağırtaş, Middle East Technical University
Oğuz Yayla, Middle East Technical University

An accountable subgroup multi-signature is a kind of multi-signature scheme in which any subgroup $\mathcal{S}$ of a group $\mathcal{G}$ of potential signers jointly sign a message $m$, ensuring that each member of $\mathcal{S}$ is accountable for the resulting signature. In this paper, we propose three novel pairing-based accountable subgroup multi-signature (ASM) schemes, which are secure against existential forgery under chosen-message attacks and computational co-Diffie-Hellman assumption. In the first one, we use Feldman’s verifiable secret sharing scheme as an implicit authentication and proof-of-possession for setting up group $\mathcal{G}$. In the second one, the members participating in authentication are decided by the subgroup. In the third one, we consider a designated combiner managing the authentication process. All schemes we propose here require fewer computations in the signature generation, signature aggregation, and verification phases than the pairing-based ASM scheme proposed by Boneh, Drijvers, and Neven. Moreover, our first and third ones solve the open problem of constructing an ASM scheme in which the subgroup $\mathcal{S}$ of signers is unknown before the signature generation. Besides, we give a method of eliminating the combiner in case of knowing the subgroup of signers $\mathcal{S}$ in advance. Further, we extend our proposed schemes to aggregated versions. For $N$ accountable subgroup multi-signatures, aggregated versions of our proposed schemes output an aggregated signature with the size of a single group ($\mathbb{G}_1$) element and require $N + 1$ pairings in aggregated signature verification. In contrast, the partially aggregated ASM scheme of Boneh, Drijvers, and Neven gives an aggregated signature with the size of $N + 1$ group elements and requires $2N + 1$ pairings in aggregated signature verification.

Available format(s)
Public-key cryptography
Publication info
multi-signatureaccountable subgroup multi-signaturepairing-based cryptography
Contact author(s)
agirtas ramazan @ metu edu tr
oguz @ metu edu tr
2023-05-16: last of 3 revisions
2022-01-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ahmet Ramazan Ağırtaş and Oğuz Yayla},
      title = {Pairing-based Accountable Subgroup Multi-signatures with Verifiable Group Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2022/018},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.