ESS signatures are de¬ned as mesh signatures in a composite-order group G.

We do require however that the “main” generator g generate only the subgroup

Gp of order p. That is, we impose that g p = 1 ∈ G or equivalently g ≡ 1 ∈ Gq .

Since the Ai , Bi , Ci , and thus the Ri , are powers of g, all those elements will

belong in the subgroup Gp of order p. It is easy to see that, since the veri¬cation

equation is of the form e(Si , Ri ) = e(h, g), both sides will always evaluate into

the target subgroup of order p, with no contribution of order q. It follows that

only the Gp components of the Si will matter for ESS veri¬cation.

In order to provide a tracing capability, we pick h as a generator of the entire

group G, hence with a non-trivial component h ≡ 1 ∈ Gq . The same will be true

for the public key “ = hγ . As a result, all the user-created atomic signatures of

1

the form S = (“ hxi ) /(...) will also contain a non-trivial component S ≡ 1 ∈ Gq ,

Expressive Subgroup Signatures 197

which has no e¬ect on the ESS veri¬cation equation, per the preceding argument.

These order-q components will be our tracers, since they appear in all atomic

signatures (which are powers of h ∈ G), but not in any of the blinding coe¬cients

(which are powers of g ∈ Gp ).

Since we now work in a composite-order group of order N , we rede¬ne the

user™s signing exponents in ZN instead of Zp .

Remark that if h had no residue of order q, then everything would be in Gp .

It would be as if the subgroup Gq did not exist, and the ESS scheme would

reduce to an information-theoretically untraceable mesh signature in Gp . As the

Decision Subgroup assumption [10] states that h ∈ G and h ∈ Gp should look

the same to an outsider, it follows that our tracing mechanism cannot be public

and will thus require some trapdoor (in this case, the factorization of N ).

3.6 Tracing Procedure

The presence of a non-trivial residue of order q in h will act as a silent tracer for

lifting the anonymity of any signature, using the factorization of N as trapdoor.

To unblind an ESS signature (ti , Si )n , the tracing authority raises each Si

i=1

to the power of p, to strip it from all components of order p. Then, for each i:

“ If the residue (Si )p = 1, there was no contribution from h in Si , hence νi = 0,

and thus the truth value of the associated literal Li is “false”. Conclusion:

user i did not participate in the creation of the ESS signature.

“ If the residue (Si )p = 1, there was some h contribution in Si , hence νi = 0,

and thus the truth value of the associated literal Li is “true”. Conclusion:

(an atomic signature issued by) user i took part in the ESS signature.

The tracer can thus e¬ciently determine the exact set of users that are involved

(and in what capacity).

We emphasize that, unlike tracing schemes in many other contexts that can

only guarantee that one of the guilty parties will be exposed, here the tracing

authority ¬nds out exactly how the signature was constructed, and thus uncovers

the identity of all of the culprits.

Notice also that such detailed “exhaustive tracing” requires signatures whose

size is (at least) linear in the size of the propositional expression. Hence, in that

respect, our scheme is optimally compact up to a constant factor.

3.7 Concurrent Join Protocol

As in [19] we can de¬ne a Join protocol, using some standard techniques: an ex-

tractable commitment (Ext-Commit), a zero-knowledge proof of equality of the

discrete logarithms (NIZKPEqDL), and a zero-knowledge proof of knowledge of a

discrete logarithm (NIZKPoKDL). During this protocol, a future group member

(Ui ) interacts with the group manager (GM), in order to obtain a valid group

certi¬cate (Ai , Bi , Ci ), with a private key (xi , yi , zi ), with (yi , zi ) not known

198 X. Boyen and C. Delerabl´e

e

by the group manager. We suppose, as in [19] that there is a separated PKI

environment: each user Ui has a personal secret key usk[i] and the corresponding

certi¬ed public key upk[i].

We refer to the full version of the paper for the details of the Join protocol.

3.8 The Full ESS Construction

The step-by-step construction outlined above gives us the complete ESS scheme.

The only operational di¬erences with the mesh signature scheme of [11]

are:

1. the setup, which asks for a bilinear group G of composite order N = pq, two

generators g ∈ Gp and h ∈ G, and a group manager™s public key “ = hγ ;

2. the existence of two additional algorithms or protocols: one for joining the

group, the other for tracing a signature.

For reference purposes, the complete ESS construction in full detail as well as

security proofs can be found in the full version of the paper. The construction

follows exactly the outline given above. Most of the technicalities are borrowed

directly from the mesh signature scheme of [11], with which the ESS scheme

shares many similarities.

4 Security

Theorem 1 (Anonymity). There is no PPT algorithm that wins the Expres-

sive Subgroup Signature anonymity game over G with advantage in time „ ,

unless the Decision Subgroup problem in G is decidable in time „ ≈ „ with

advantage ≥ /2.

Theorem 2 (Traceability). There is no PPT algorithm that wins the Expres-

sive Subgroup Signature traceability game over G with advantage in time „ ,

unless the Decision Subgroup problem is decidable in time „ with advantage ,

and mesh signatures in Gp can be existentially forged in time „ with advantage

, where „ + „ ≈ „ and + ≥ /2.

5 Conclusion

In this work, we have proposed a new generalization of the notion of group

signatures, that allows signers to cover the entire spectrum from complete dis-

closure to complete anonymity. Previous group signature constructions did not

provide any disclosure capability, or at best a very limited one (such as subset

membership). Our scheme o¬ers a very powerful language for disclosing exaclty

in what capacity a subgroup of signers is making a signature on behalf of the

group.

Expressive Subgroup Signatures 199

References

1. Ateniese, G., Camenisch, J., Hohenberger, S., de Medeiros, B.: Practical group

signatures without random oracles. Cryptology ePrint Archive, Report 2005/385

(2005), http://eprint.iacr.org/

2. 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)

3. Ateniese, G., Song, D.X., Tsudik, G.: Quasi-e¬cient revocation in group signatures.

In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 183“197. Springer, Heidelberg

(2003)

4. Ateniese, G., Tsudik, G.: Some open issues and new directions in group signatures.

In: Franklin, M. (ed.) FC 1999. LNCS, vol. 1648, pp. 196“211. Springer, Heidelberg

(1999)

5. Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: Formal

de¬nitions, simpli¬ed requirements, and a construction based on general assump-

tions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614“629.

Springer, Heidelberg (2003)

6. 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)

7. Bender, A., Katz, J., Morselli, R.: Ring signatures: Stronger de¬nitions, and con-

structions without random oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006.

LNCS, vol. 3876, pp. 60“79. Springer, Heidelberg (2006)

8. Boneh, D., Boyen, X.: Short signatures without random oracles. In: Cachin, C.,

Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 56“73. Springer,

Heidelberg (2004)

9. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.)

CRYPTO 2004. LNCS, vol. 3152, pp. 41“55. Springer, Heidelberg (2004)

10. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In:

Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325“341. Springer, Heidelberg

(2005)

11. Boyen, X.: Mesh signatures. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS,

vol. 4515, pp. 210“227. Springer, Heidelberg (2007)

12. Boyen, X., Waters, B.: Compact group signatures without random oracles. In:

Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 427“444. Springer,

Heidelberg (2006)

13. 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)

14. Camenisch, J.: E¬cient and generalized group signatures. In: Fumy, W. (ed.) EU-

ROCRYPT 1997. LNCS, vol. 1233, pp. 465“479. Springer, Heidelberg (1997)

15. Camenisch, J., Groth, J.: Group signatures: Better e¬ciency and new theoretical

aspects. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 120“133.

Springer, Heidelberg (2005)

16. Camenisch, J., Lysyanskaya, A.: Dynamic accumulators and application to e¬cient

revocation of anonymous credentials. In: Yung, M. (ed.) CRYPTO 2002. LNCS,