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

that, in our case, new coupons can be added at any time (at home, for instance),
without any problem.
This article thus provides fundamental building blocks for the deployment of
low-power privacy preserving applications, in contexts where the nodes involved
in the applications cannot perform heavy computations, which is the case most
of the time for the moment.

Outline. After a brief reminder on group signatures (Section 2), we extend the
standard security properties to the cooperative setting (Section 3). Next, we
present our cooperative XSGS protocol and prove its security with respect to
our new security definitions (Section 4). We eventually demonstrate that our
protocol can be executed on small devices, by presenting and discussing the
performance of its implementation on small wireless sensor devices, of which the
controllers are also sometimes included in RFID tags (Section 5).

2 Definition of Group Signature Schemes

In [9], Chaum and van Heyst introduce the notion of group signature
schemes [1,3,17,14,5,22] where members of the group can sign documents and
any verifier can confirm that the signature comes from a group member. More-
over, group signatures are anonymous and unlinkable for every verifier except
for a given authority.

2.1 Generic Description of Group Signatures

GS

Formally speaking, a group signature scheme is described by the following

polynomial-time procedures, where λ is a security parameter.

- GenParam is a probabilistic algorithm which takes as input 1 λ and which
outputs the public parameters of the system PP =( Gpk , Rpk , params )where
Gpk is the group's public key, Rpk is the public key of the opening manager
and params are public parameters (e.g. mathematical groups, generators,...),
it also outputs the group manager's secret key gmsk and the opening man-
ager's secret key rsk ;
- UserKeyGen is a probabilistic algorithm which attributes to a user a pair
of secret/public key ( usk , Upk ) respecting a PKI.
- Join is a probabilistic protocol between the group manager and a new group
member U i to provide the latter with his group secret key gsk [ i ]. The group
manager makes an entry Tab [ i ] in the registration table Tab ,withtheentire
transcript of the process.
- Sign is a probabilistic algorithm which takes as input a secret signing key
gsk [ i ] and a message m and returns the group signature σ on m ;
- Verif is a deterministic algorithm which takes as input a message m ,and
asignature σ and returns either 1 if the signature is valid or 0 otherwise;