Paper 2011/376

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

Julien Bringer and Alain Patey


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.

Available format(s)
Publication info
Published elsewhere. SECRYPT 2012
Group SignaturesVerifier-Local RevocationBackward UnlinkabilityExculpabilityEfficiencyRevocation Check
Contact author(s)
julien bringer @ gmail com
2012-05-14: revised
2011-07-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julien Bringer and Alain Patey},
      title = {Backward Unlinkability for a VLR Group Signature Scheme with Efficient Revocation Check},
      howpublished = {Cryptology ePrint Archive, Paper 2011/376},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.