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

Table 2. Storage requirements (in bytes) of our implementation on the sensor nodes.
In coupon mode, 21 B must be added per stored coupon.

Mode Memory MICAz TelosB

Coupon RAM 1067 (26%) 1071 (10%)

ROM 23764 (18%) 14470 (29%)

No Coupon RAM 1699 (41%) 1739 (17%)

ROM 36576 (28%) 19164 (39%)

The original XSGS protocol would also consume a considerable amount of
memory. On the other hand, the memory usage of the cooperative protocol is
relatively modest (Table 2), even when the ECC point multiplication is per-
formed on the node. The tiny operating system already consumes a significant
fraction of the used memory (about 700 B RAM and a little more than 10 kB
ROM on both nodes). A coupon ( r z , r z . Rpk 1 ) requires normally 60 B, i.e. three
20-B field elements, but it can be reduced to a little more than 20 B using point
compression and a PRNG sequence for storing all the r z , as done in [20]. As
the coupons can be placed in RAM or ROM, their storage in both the MICAz
and TelosB is not a problem. Considering the available memory resources, the
MICAz and the TelosB could be filled with more than 5000 and 2500 coupons
respectively, which is more than practical for many applications.

References

1. Ateniese, G., Camenisch, J., Joye, M., Tsudik, G.: A practical and provably secure
coalition-resistant group signature scheme. In: Bellare, M. (ed.) CRYPTO 2000.
LNCS, vol. 1880, pp. 255-270. Springer, Heidelberg (2000)
2. Bellare, M., Shi, H., Zhang, C.: Foundations of group signatures: The case of dy-
namic groups. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 136-153.
Springer, Heidelberg (2005)
3. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M.K.
(ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41-55. Springer, Heidelberg (2004)
4. Boneh, D., Boyen, X.: Short signatures without random oracles and the sdh as-
sumption in bilinear groups. J. Cryptology 21(2), 149-177 (2008)
5. Boyen, X., Waters, B.: Full-domain subgroup hiding and constant-size group sig-
natures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 1-15.
Springer, Heidelberg (2007)
6. Brickell, E.F., Camenisch, J., Chen, L.: Direct anonymous attestation. In: ACM
Conference on Computer and Communications Security 2004, pp. 132-145 (2004)
7. Camenisch, J., Groth, J.: Group signatures: Better eciency and new theoretical
aspects. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 120-133.
Springer, Heidelberg (2005)
8. Canard, S., Girault, M.: Implementing group signature schemes with smart cards.
In: CARDIS 2002, pp. 1-10. USENIX (2002)
9. Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT
1991. LNCS, vol. 547, pp. 257-265. Springer, Heidelberg (1991)