At any time a member can decide to leave the group. In this case,
we can reasonably think that he will not try to cheat in the
future, but it is far from sure. Furthermore if a member is
revoked from the group against his will, it is very plausible that
he will try to keep on signing even if he has not the right to
anymore. In both cases, it is necessary to set up a mechanism
which prevents this type of fraud.
The paper of E. Bresson and J. Stern [4] proposed the most
intuitive solution which consists for the signer in proving that
he is different from any revoked member. But this method obviously
generates a signature whose size linearly increases according
to the number of revoked members.
In a recent paper, Song [14] proposed two revocation methods
that are relatively similar and provide constant-length signatures
and a constant work for the group manager. But the work of the
verifier is also linear in the number of revoked members.
Moreover, the solution is not very practical since it deals with a
group with a limited life-expectancy.
Ateniese, Song and Tsudik [2] proposed a modification of
the Ateniese et al. scheme [1] to improve member
revocation, which also provides a constant size of signature. But
works during the revocation phase and the verification one are
linear in the number of revoked members. Finally, the cost of the
signature is very expensive and consequently it is an
overall unpractical solution.
Very recently, Camenisch and Lysyanskaya [5] proposed the
first practical method for member revocation. It is also based on
the scheme of Ateniese et al. [1] and therefore is not
really generic (i.e. cannot be easily applied to any other group
signature scheme). Moreover the signer has to make (possibly
off-line) a number of modular exponentiations which is
proportional to the number of modifications in the group (addition
or deletion) until his last signature. Finally, this solution
implies additional proofs of knowledge and, consequently, many
other modular exponentiations.