Cryptology ePrint Archive: Report 2011/376

Backward Unlinkability for a VLR Group Signature Scheme with Efficient Revocation Check

Julien Bringer and Alain Patey

Abstract: Verifier-Local Revocation (VLR) group signatures, introduced by Boneh and Shacham in 2004, are a particular case of dynamic group signature schemes where the revocation process does not influence the activity of the signers. The verifiers use a Revocation List to check if the signers are revoked. In all known schemes, checking a signature requires a computational time linear in the number of revoked members. Usually, it requires one pairing per revoked user. Recently, Chen and Li proposed a scheme where Revocation Check uses exponentiations instead of pairings. In this paper, we first propose a correction of their scheme to enable a full proof of the traceability property. Then our main contribution is to extend this tweaked scheme to ensure Backward Unlinkability. This important property prevents the loss of anonymity of past signatures when a user is revoked. We succeed in achieving this consequent improvement with a constant additional cost only. We thus obtain the scheme with the most efficient Revocation Check among VLR schemes enabling Backward Unlinkability.

Category / Keywords: Group Signatures, Verifier-Local Revocation, Backward Unlinkability, Exculpability, Efficiency, Revocation Check

Publication Info: SECRYPT 2012

Date: received 11 Jul 2011, last revised 14 May 2012

Contact author: julien bringer at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20120514:133910 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]