Group signature schemes with membership revocation for large groups

Toru Nakanishi, Nobuo Funabiki

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


Group signature schemes with membership revocation have been intensively researched. However, signing and/or verification of some existing schemes have computational costs of O(R), where R is the number of revoked members. Existing schemes using a dynamic accumulator or a similar technique have efficient signing and verifications with O(1) complexity. However, before signing, the signer has to modify his secret key with O(N) or O(R) complexity, where N is the group size. Therefore, for larger groups, signers suffer from enormous costs. On the other hand, an efficient scheme for middle-scale groups with about 1,000 members is previously proposed, where the signer need not modify his secret key. However this scheme also suffers from heavy signing/verification costs for larger groups with more than 10,000 members. In this paper, we adapt the middle-scale scheme to larger groups ranging from 1,000 to 1,000,000 members. At the sacrifice of the group manager's slight cost, our signing/verification is sufficiently efficient.

Original languageEnglish
Pages (from-to)1275-1283
Number of pages9
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number5
Publication statusPublished - May 2006


  • Group signature schemes
  • Membership revocation
  • Signatures of knowledge
  • Strong RSA assumption

ASJC Scopus subject areas

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'Group signature schemes with membership revocation for large groups'. Together they form a unique fingerprint.

Cite this