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

29. Naccache, D., M'Raıhi, D., Vaudenay, S., Raphaeli, D.: Can D.S.A. Be improved?
In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 77-85. Springer,
Heidelberg (1995)
30. Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic
applications. In: STOC, pp. 33-43. ACM, New York (1989)
31. Oliveira, L.B., Scott, M., Lopez, J., Dahab, R.: Tinypbc: Pairings for authenti-
cated identity-based non-interactive key distribution in sensor networks. In: 5th
International Conference on Networked Sensing Systems, INSS 2008, pp. 173-180
(June 2008)
32. Paillier, P.: Public-key cryptosystems based on composite degree residuosity
classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223-238.
Springer, Heidelberg (1999)
33. Schnorr, C.-P.: Ecient identification and signatures for smart cards. In: Brassard,
G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239-252. Springer, Heidelberg (1990)
34. TexasInstruments. Texas Instruments Government Electronic Identification (April
2010), http://www.ti.com/rfid/docs/manuals/brochures/govid_trifold.pdf
35. TinyOS. An open-source operating system designed for wireless embedded sensor
networks (April 2010), http://www.tinyos.net/
36. Xu, S., Yung, M.: Accountable ring signatures: A smart card approach. In: CARDIS
2004, pp. 271-286. Kluwer, Dordrecht (2004)

A XSGS Group Signature

In this section, we give some useful tools and next focus on the XSGS group
signature scheme, using additive notations.

A.1 Some Notations and Tools
Bilinear Groups. Let G T be multiplicative cyclic groups of prime

order q and let ψ be an isomorphism from

G 1 , G 2 and

G 2 to G 1 . G 1 (resp. G 2 )isagenerator

of G 1 (resp. G 2 ). Finally, let e be a computable bilinear map G 1 × G 2 −→ G T such

that e ( G 1 ,G 2 ) = 1 and for all P 1 ∈ G 1 , P 2 ∈ G 2 and a, b ∈ Z , e ( a.P 1 ,b.P 2 )=

e ( P 1 ,P 2 ) ab .( q, G 1 , G 2 , G T ,G 1 ,G 2 ,e,ψ ) is called a bilinear environment.

Zero-Knowledge Proofs of Knowledge. Roughly speaking, a Zero Knowl-
edge Proof of Knowledge (ZKPK) is an interactive protocol during which an
entity P proves to a verifier V that he knows a set of secret values α 1 ,...,α q
verifying a given relation R without revealing anything else. These protocols
are also used to prove that some public values are well-formed from secret val-
ues known by the prover. It is possible to transform these protocol into non-
interactive proof of knowledge, generally called signature of knowledge, using
the Fiat-Shamir heuristic [16].
In the sequel, we denote by SoK ( α 1 ,...,α q : R ( α 1 ,...,α q )) a signature of
knowledge of the secrets α 1 ,...,α q verifying the relation R . We also define π as
the interactive protocol between a prover P , on input α 1 ,...,α q and R and a

verifier V on input R and which allows P to prove that she knows the secrets in

a zero-knowledge manner. The output of V is either 1 if the prover is accepted

and 0 otherwise.