Paper 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.