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

Group Signatures are Suitable for Constrained
Devices

Sebastien Canard 1 , ,IwenCoisel 2 , ,
Giacomo De Meulenaer 2 , , and Olivier Pereira 2

1 Orange Labs - 42 rue des Coutures - BP6234 - F-14066 Caen Cedex - France
[e-mail]
2 Universite Catholique de Louvain - B-1348 Louvain-la-Neuve - Belgium
{ iwen.coisel,giacomo.demeulenaer } @uclouvain.be

Abstract. In a group signature scheme, group members are able to
sign messages on behalf of the group. Moreover, resulting signatures are
anonymous and unlinkable for every verifier except for a given author-
ity. In this paper, we mainly focus on one of the most secure and e-
cient group signature scheme, namely XSGS proposed by Delerablee and
Pointcheval at Vietcrypt 2006. We show that it can e ciently be imple-
mented in a sensor node or an RFID tag, even if it requires 13 elliptic
curve point multiplications, 2 modular exponentiations and one pairing
evaluation to produce a group signature. This is done by securely out-
sourcing part of the computation to an untrusted powerful intermediary.
The result is that XSGS can be executed in the MICAz (8-bit 7.37MHz
ATmega128 microprocessor) and the TelosB (16-bit 4MHz MSP430 pro-
cessor) sensor nodes in less than 200 ms.

Keywords: Constrained devices, server-aided computation, group sig-
nature, anonymity.

1 Introduction

Group signatures have been introduced by Chaum and van Heyst [9], and showed
to be extremely useful in various applications such as anonymous credentials, e-
cash, e-vote and identity management. These signatures allow any member of
a group to sign a document and any verifier to confirm that the signature has
been computed by a group member. Moreover, group signatures are anonymous
and unlinkable for every verifier except, when needed, for a given authority.
While being very appealing, implementing these signature schemes on low-power
devices, like sensor nodes or RFID tags, appears to be a particularly challenging
task, as the computation of a signature typically requires numerous modular
exponentiations or pairing evaluations. For instance, it is necessary to compute
13 elliptic curve point multiplications, 2 modular exponentiations and 1 pairing

Supported by French ANR PACE project.
Supported by Walloon Region project SEE.
Supported by Walloon Region project Nanotic.