Revocable Group Signatures with Compact Revocation List Using Accumulators

Toru NAKANISHI  Nobuo FUNABIKI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E98-A   No.1   pp.117-131
Publication Date: 2015/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E98.A.117
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Public Key Based Cryptography
Keyword: 
anonymity,  group signatures,  revocations,  accumulators,  

Full Text: PDF(635KB)>>
Buy this Article




Summary: 
A group signature scheme allows a group member to anonymously sign a message on behalf of the group. One of the important issues is the member revocation, and lots of revocable schemes have been proposed so far. A scheme recently proposed by Libert et al. achieves that O(1) or O(log N) efficiency of communication and computation except for the revocation list size (also the revocation cost), for the total number of members N and the number of revoked members R. However, since a signature is required for each subset separated from the set of non-revoked members, the size is about 900R Bytes in the 128-bit security. In the case of R=100,000, it amounts to about 80MB. In this paper, we extend the scheme to reduce the revocation list (also the revocation cost), by accumulating T subsets, which is signed for the revocation list. The revocation list size is reduced by 1/T. Unfortunately, the public key size, membership certificate size and the cost of a witness computation needed for signing increase related to T.