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)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]