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

Table 1. Running times of the various phases of the cooperative XSGS protocol. The
on-line phase of the sign procedure takes less than 200 ms.

Phase Detail Time (ms)

Off-line Sign

Prover (MICAz) 3800

Prover (TelosB) 6400

Intermediary 195

On-line Sign

Prover (MICAz) 7

Prover (TelosB) 9

Intermediary 65

Communication 120

< 200

Total

Verify - 55

Open - 35

intermediary side, the computations were implemented in C using the GMP [21]
library and the PBC library to achieve the pairings. They took place on a laptop
equipped with a 64-bit 1.4 GHz Intel Core 2 Duo. The pairing computations were
rather fast in this setting: 11 ms were su cient to perform a Tate pairing.
The running times for the various parts of the sign procedure are given in
Table 1. The on-line phase of the protocol is performed in less than 200 ms with
both sensor nodes. The communication delay and the intermediary computations
are the main components of the on-line phase latency. The time required by the
prover computations, i.e. , the calculation of s z , is marginal ( < 10 ms).
In the off-line phase, the computation of the point multiplication giving P 6
lasts about 4 and 6 seconds on the MICAz and TelosB respectively. While rea-
sonably ecient, the TinyECC library, on which our implementation is based,
is however significantly slower than recently proposed ECC implementations on
sensor nodes. We therefore expect the point multiplication to be significantly
faster using the same techniques as for instance the implementation proposed
in [23], which performs a fixed-base point multiplication in less than a second
on a 192-bit elliptic curve group. As a result, even if the prover device has to
compute the point multiplication P 6 during the on-line phase, the whole proce-
dure can be done within a few seconds (much less if a dedicated hardware ECC
engine is available on the tag).
The fast on-line phase of the cooperative protocol makes group signatures
of practical interest for small devices like contactless smart cards. By contrast,
signing with the original XSGS protocol would require a much longer interaction
between the passive device and the reader. To give a rough idea, a pairing eval-
utation takes about 5.5 second on the MICAz (with the TinyPBC library [31])
and an ECC point multiplication requires 0.71 second with the implementation
from [23] (there are 13 of these in XSGS): the whole protocol would take on the
order of 15 seconds with the MICAz.