Group signatures allow any member of the group sign the message on behalf of the group anonymously using his own secret-key. Only group manager can reveal the identity of the signer. Verifier Local Revocation (VLR) is an efficient approach of membership revocation.

In VLR group signatures, revocation-token is generated for each user and is placed in Revocation List (RL) whenever the user is revoked. VLR group signature schemes consist of three algorithms: KeyGen, Sign and Verify

KeyGen algorithm outputs public-key, secret-key for each user and revocation-token for each user

Sign algorithm generates the signature on a message using the secret-key of a group member.

Verify algorithm returns 1 if it is a valid signature that is signer is valid group member and he is not revoked. Otherwise, returns 0.

If a group member "i" is revoked then its revocation token in placed RL. Therefore, he cannot generate a valid signature. But, the verify algorithm returns invalid for all the signatures generated by user "i" before revocation if we verify the signatures using the RL where revocation-token of user "i" is placed. Is my understanding correct?


1 Answer 1


I think it depends on the implementation of the scheme. A naive implementation might do what you've described and invalidate every previous signature of the revoked member.

However, the scheme proposed here: http://www.scitepress.org/Papers/2012/40175/40175.pdf takes a respective time $period$ into account.

Here the verification algorithm is defined as:

$Verify(gpk, j, RL_{j}, m , \sigma)$:

This algorithm, run by a verifier takes as input a message $m$, its signature $\sigma$, a period $j$, the corresponding Revocation List $RL_{j}$ and the public parameters $gpk$. It checks if the message has been signed by an unrevoked group member, without revealing the signer’s identity. The possible outputs are valid and invalid.

As you can see, the verification check depends on a certain time period here. In this case, all signatures in previous periods would remain valid. This is especially useful because it enables to unrevoke members in a later period without having to generate a new key for that user.

So to answer your question: I think it depends on the implementation.

  • $\begingroup$ In verify algorithm, time period $j$ refers to the current time interval or the time interval in which the signature is generated. Assume a signature was generated in time interval $j-1$ and it is being verified in time interval $j$ (current time interval) verify algorithm returns valid. If $j$ is the time in which signature is generated then any revoked member can sign the messages for their past time periods. $\endgroup$
    – preethi
    May 6, 2019 at 23:58
  • $\begingroup$ Well backdating is a problem with digital signatures in general, I think. To mitigate this, what you want to do is to use a trusted time-stamping authority in the signing process. Basically, you have a trusted service that issues authenticated timestamps which you have to put into your signatures. Obviously the time-stamping authority won't issue timestamps that are in the past. That way during verification the verifying parties can also check the timestamp (they know the root certificate of the authority). Then no members (revoked or not) could not generate signatures for past periods. $\endgroup$
    – grees
    May 7, 2019 at 5:29
  • $\begingroup$ Oh and if you are wondering how reusing of previous timestamps is mitigated: Trusted time-stamping requires you to send a hash of the data to the time-stamping authority (TSA). The TSA then concatenates, the hash of the data with the timestamp and calculates the hash of this concatenation. The resulting hash is then signed by the TSA. The signed hash and the timestamp is returned to the client. Now the timestamp is bound to the data, i.e., you cannot use this timestamp in combination with any other data. $\endgroup$
    – grees
    May 7, 2019 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.