The first solution is straightforward and Figure 5 shows its principle. It consists in having the whole ``black list'' signed by the GM. Assuming that the underlying hash function of the signature scheme is iterative (most of them are so), it is possible for the smart card to verify the signature of a large message without needing to keep the entire message in his memory.
Note that it is possible to use this method in a context of ``white list'' (that is a list which contains the identifiers of all members). In this case the card accepts to sign only if its identifier is in the list. It can be useful if the group has few members but a lot of revocations. We do not treat this case in this paper as it is an easy adaptation of the ``black list'' case.
