Group Signature Scheme without Opening but with Revocation

Question

After reading many papers about group signature schemes, I saw that basically all of them employ the possibility of "signature opening": The Group Manager (GM) can identify any signature made by his group's members. But I would like to completely eradicate that feature and rather revoke group members by their public key/ID token, preserving signature anonymity at all times.

(I am thinking about very dynamic and large groups with their members "expiring" after a certain time: the GM keeps a public key list and revokes keys when they expire. Maybe existing cryptography is not scalable enough for that yet, though.)

An option would be to take a GSS that seperates the issuer GM and the opener GM and just throw away the opener's key. But that gives me two issues:

• Firstly, the users should stay anonymous even if the GM (the server) is compromised.
• Secondly, existing GSS do not actually seperate the opener's and the revoker's key, but since I need to revoke users' access rights, this is unfeasible.

Is there any such GSS that satisfies my security requirements? Are there any existing GSS that I could alter a little bit to remove the opening ability - preserving their security proof - and use? Are there entirely other options?

(The actual problem giving me headaches is more general security related and I didn't want to explain it here because it is rather complex. But if you have any further questions about my requirements, please go ahead!)

Answer 1

(If members "expiring" is the only reason for revocation, then you could just skip the whole "standard signature scheme" part of the following, encode the expiration dates into the IDs, and have the signers' arguments include that issue too.)


Well, there's always the generic approach:

• the GM generates a common reference string for an otherwise-noninterative computationally witness-indistinguishable system that is co-sound as a stand-alone argument of knowledge; i.e., it's infeasible to give a valid argument for any statement that it would be infeasible to know a witness for

• the GM chooses a function from a collision-resistant hash family

• the GM generates a two inner key-pairs, one for a standard signature scheme and one for an identity-based signature scheme

• the GSS's public key is the ordered quadruple whose entries are the common reference string and the collision-resistant hash function and the inner public keys

• the GM's private key is the ordered pair whose entries are the inner private keys

• the GM uses the standard signature scheme for signing [the root hash of a Merkle tree of the result of sorting the revoked identities] along with [other information, such as a date], and regularly gives out that signature along with that sorted list, similarly to how CRLs are issued in standard implementations of PKI

• for users issuing and verifying signatures, let "the sro" denote the most recent version known to the signer of the previous bullet point's signature together with [the root hash ... revoked identities] and the specified other information

• the GM issues for the GSS by issuing for the identity-based signature scheme

• users sign by generating a key-pair for a strongly unforgeable one-time signature (OTS) scheme, choosing enough information to specify what Identity Revocation List to use, arguing knowledge of a signature on the OTS verification key by an identity and two branches through the tree witnessing that the identity is not on the list, using the OTS signing key to sign the ordered triple whose entries are the sro and the argument and the message, and letting the signature be the ordered quadruple whose entries are the sro and the OTS verification key and the argument and the OTS signature

• receivers verify by verifying the signature on the sro, verifying that its "other information" is appropriate (specifically, it's date is recent enough), verifying the argument for the sro and the OTS verification key and the message, and then verifying the OTS signature

The main problem with this approach is the size of the witness-indistinguishable arguments.

If you use the modification of figure 3 in this link obtained by replacing $K_{\text{binding}}$ with $K_{\text{hiding}}$,
then the existence of a witness that the commitment key is hiding suffices for perfect anonymity.
Thus, you could have the GM keep such a witness and give concurrent zero-knowledge proofs that such a witness exists.

There are apparently lots of identity-based signature schemes that can work in bilinear groups.
It is possible that the type of system described in this paper can be adapted to such a scheme. $\:$ Although I'm not sure, it seems likely that NIZK co-sound arguments constructed from the previous two sentences could provide the same anonymity as I mentioned in the previous paragraph.

This paper gives a NIZK protocol with whose use in this approach comes with a trade-off:
soundness is based on the generic bilinear group model (analogous to the Random Oracle Model),
but by having users verify the common reference string's structure as described on page 3,
perfect anonymity is guaranteed without needing to trust or interact with the GM.


I have not managed to come up with any scheme for what you
are asking about that does not use a non-interactive argument.