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

to produce a DLIN based eXtremely Short Group Signature (XSGS) [14], one
of the most ecient and powerful schemes available today.
In this paper, we design a cooperative variant of the XSGS group signature
scheme [14]. Our result is ecient enough to permit the group member to be
associated to a constrained device which interacts with an intermediary (which
can belong to the group member, e.g. a personal computer).
Related Work. The way to embed cryptography into low-power devices has been
largely studied by the cryptographic community. One solution is to make pre-
computations but this has the drawback of consuming a lot of memory space
and thus simply shifts the problem. Another possibility is to modify the crypto-
graphic mechanism to fit the device restrictions. This has already been done in
the RFID case [19,15] or when considering the integration of group signatures in
a smart card [8,36]. This may necessitates important modifications of the initial
algorithm, and may imply some stronger (and questionable) assumptions such
as,e.g.,tamper-resistance.
In this paper, we focus on a second approach, which consists in studying how
a more powerful entity can help a small device to provide a group signature,
as introduced in [27] and later used for DAA in e.g. [6]. Another approach has
also been taken in the CAFE project [10,11], which consists in designing schemes
where a powerful prover interacts with a non-trusted smart card to perform some
computations in such a way that the prover is unlinkable w.r.t. the smart card.
Our Contributions. The introduction of an intermediary device in a signature
scheme must be carefully understood if one wants to avoid introducing severe
security flaws in the system. Our contribution in this direction is threefold.
To begin with, we propose the first complete security model for coopera-
tive group signatures. Our model allows clarifying the exact level of trust that is
placed into the intermediary, this trust directly impacting the amount of compu-
tation that can be outsourced by the tag. The trust we place in the intermediary
is quite limited: even compromised, it is not able to impersonate the signer. With
this property, the security of standard group signature systems can be improved:
the group members' secrets can be stored in well-protected embedded devices
like contactless smart cards instead of being present in their personal computer,
which may be unsecure (e.g. infected with a trojan).
Then, we propose a new cooperative group signature scheme, based on the
XSGS protocol [14], and prove its security in our model. Our scheme is ecient
enough to be implemented on small embedded devices.
We demonstrate this by documenting implementation results on two common
wireless sensor nodes, the MICAz and the TelosB sensor nodes, the processor of
the TelosB node being also used in contactless secure government electronic ID
chips. The on-line phase of the protocol can be completed in less than 200 ms.
The off-line phase requires four to six seconds to be completed, but this can be
mitigated with a coupon mode (from [29] and the EU project CAFE ESPRIT
7023), which allows a node to pre-compute or pre-load up to 5000 coupons in
advance, while satisfying the memory constraints of our devices. We also show