Shared Private Key and Smart Card

Our solution consists in using a smart card and a group-shared private key. First of all, we must choose an ordinary signature scheme (keys $SK_G$ and $PK_G$) and a semantically secure cryptosystem (keys $D_{Aut}$ and $E_{Aut}$), which is a cryptosystem where the ciphertext does not leak any partial information whatsoever about the plaintext that can be computed in expected polynomial time (and consequently, it is a probabilist cryptosystem). Then, the group manager computes keys in such a way that he can keep secret private ones ($D_{Aut}$) or distribute them ($SK_{G}$) to members without knowing them (for example, several group managers can share a discrete logarithm as the private key). He publishes public keys ($PK_{G}$ and $E_{Aut}$).
If Alice wants to become a new group member, she firstly has to hold a smart card. Then, she has to obtain from the group manager an identifier $z$ (which is unique and that identifies her) and the shared private key $SK_{G}$ (which is common to all group members). Alice's smart card also has access to all parameters so as to use the cryptosystem (among which $E_{Aut}$) and the signature scheme defined above. The group manager has to keep in mind the link between the identifier (i.e. $z$) and the identity of the group member (i.e. Alice).
When Alice wants to sign a message as a group member (see Figure 1), she has to use her smart card. First, the identifier $z$ is encrypted (algorithm $EA$) with the group manager's public key $E_{Aut}$ (so that the group manager is the only one who can decrypt). Then the message $M$ is concatenated with this encrypted value $C$ and the whole is signed with the help of (algorithm $SA$ and) the shared private key $SK_{G}$. As a consequence, only group members can sign a message and everybody is able to verify the signature with the associated public key $PK_{G}$.

Figure 1: Shared Private Key and Smart Card

$M$ = Message

$\Vert$ = Concatenation algorithm

$z$ = Member's identifier

$M'$ = Concatenation of $M$ and $C$

$EA$ = Encryption algorithm

$SA$ = Signature algorithm

$E_{Aut}$ = GM's encryption key

$S_{G}$ = Signature of the message

$C$ = Encryption of the identifier

$SK_{G}$ = Group-shared signature private key

The verifier obtains the encrypted value $C$, the message $M$, and the signature $S_{G}$ of the whole. He only has to verify the signature to be sure that the message is sent by a group member (because only group members possess the group-shared private key used to compute the signature). The group manager can open the signature by decrypting the identifier (with the key $D_{Aut}$).
It is important to note that the encryption scheme can either be symmetric or asymmetric. Nevertheless, it must be probabilist. On the contrary, it is necessary to use an (asymmetric) signature scheme for obvious reasons.
This approach makes possible a very fast signature, since there is only one encryption and one ordinary signature to compute. Consequently, our solution is much better than previous ones in terms of speed and memory and in terms of genericity (any signature scheme can be employed).
Furthermore, it can be used in an on-line/off-line manner as follows : first of all, the card precomputes several encrypted values C in an off-line phase. Then, by using an on-line/off-line signature scheme SA, the card can precompute some values in an off-line phase, and later (in the on-line phase) produce group signatures very quickly, for example by doing a single multiplication if using the algorithm known as GPS ([10] and [13]).