Group signature schemes with membership revocation for large groups

Toru Nakanishi, Fumiaki Kubooka, Naoto Hamada, Nobuo Funabiki

Research output: Contribution to journalConference articlepeer-review

12 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. In this paper, we adapt the middle-scale scheme to the larger groups. At the sacrifice of the group manager's cost, our signing/verification has only O(1) complexity.

Original languageEnglish
Pages (from-to)443-454
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - Oct 18 2005
Event10th Australasian Conference on Information Security and Privacy, ACISP 2005 - Brisbane, Australia
Duration: Jul 4 2005Jul 6 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


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

Cite this