Group Signatures are Suitable for Constrained Devices - Information Security and Cryptology-ICISC 2010 - page 136

- Open is a deterministic algorithm which takes as input the opening manager
secret key rsk , the registration table Tab , a message m and a signature σ and
returns either an identity i or the symbol ⊥ to indicate a failure, together

with a proof τ of this claim;
- Judge is a deterministic algorithm which takes as input the registration
table Tab , a message m , a signature σ ,anidentity i and a proof τ and returns
1 if the proof τ is a valid proof that user i has produced the signature σ and
0otherwise.

2.2 Security Properties

We outline the formal security properties from the BSZ model, introduced by
Bellare et al. [2], that are expected for (dynamic) group signature schemes.

- Correctness: a signature produced by a valid user U i must be accepted by a
verifier. Furthermore, the opening of this signature must return the identity
of U i and the judge must validate this opening.
-Anonymity: given several signatures of a user (randomly chosen among two
users), it is infeasible to distinguish which of these two users have produced
this set of signatures.
- Traceability: it is infeasible to produce a valid signature which cannot
be opened or where the proof outputted by Open cannot be verified. This
property must be verified even if several users and the group manager collude.
- Non-Frameability: it is infeasible, even for the opening and the group
manager, to claim falsely that a signature has been produced by a user.

To prove that a scheme ensures these properties, Bellare et al. [2] define for
each of these properties an experiment played by an adversary. Depending on
the concerned property, the adversary has several possibilities to interact with
the system. For example, an adversary can corrupt some users and thus obtains
their group secret keys. In some cases, the group manager can be corrupted and
thus the adversary can play his role during a Join procedure. All the possible
interactions are realized through oracles which are listed below. Moreover, a list
of honest users HU and one of corrupted users CU are needed.

- O CreateU : this oracle generates a new user i using UserKeyGen .

O AddU ( i ): this oracle adds a new user i in the group using UserKeyGen
and the interactive protocol Join . The identity of this new user is added to
the list

-

HU . The new public key Upk i is outputted.

O SJoin ( i ): during the request to this oracle, the adversary will play the role
of the group manager during a Join protocol with a new honest user. First
of all, the oracle generates a new user i with UserKeyGen and simulates
him during the protocol with the adversary. This new user is added to

-

HU .

O UJoin : this oracle simulates the group manager during a Join protocol where
the adversary plays the role of the user.

-