Group signature schemes with membership revocation for large groups

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.