order, whose cryptographic applications were ¬rst investigated in [10].

A (symmetric) composite-order pairing is an e¬ciently computable function

e : G — G ’ GT , where G and GT are ¬nite cyclic groups of order N = pq, and

with the following properties:

Bilinearity: ∀u, v ∈ G, ∀a, b ∈ Z, we have e(ua , v b ) = e(u, v)ab mod N .

Non-degeneracy: ∃g ∈ G such that e(g, g) has order N and thus generates GT .

Although the composite group order N can be made public, it is usually impor-

tant that the factorization N = pq remains a secret. The most common hardness

assumption that relies on hardness of factoring in the context of bilinear maps

is called the Decision Subgroup assumption.

188 X. Boyen and C. Delerabl´e

e

The Decision Subgroup Assumption. Let G be a bilinear group of order

N = pq. Let Gp be the subgroup of points of order p with no residue of order q,

that is, u ∈ Gp i¬ up = 1 ∈ G. Similarly, we let Gq be the subgroup of points of

order q congruent to 1 in Gp .

Informally, the decision subgroup assumption says that one cannot e¬ciently

distinguish G from Gp with non-negligible advantage.

Formally, we consider an “instance generator” G, which, on input 1» , outputs

a tuple (p, q, G, GT , e), where p and q are random »-bit primes, G and GT are

cyclic groups of order N = pq, and e : G — G ’ GT is a bilinear pairing. The

subgroup decision problem is, given (N, G, GT , e) derived from an execution of

G(1» ), to decide whether a given element w was chosen randomly in G or in Gp .

The Subgroup Decision assumption states that this is infeasible in polynomial

time with non-negligible probability above 1/2, that of a random guess.

An alternative de¬nition is to give the distinguisher two reference generators

gN ∈ G and gp ∈ Gp in addition to (N, G, GT , e) and w; the task remains to

decide whether w ∈ G or w ∈ Gp . We use this de¬nition to simplify our proofs.

The Poly-SDH Assumption. The traceability proof of the ESS scheme will

be based on the unforgeability of the mesh signature scheme of [11], which was

itself proved from the so-called Poly-SDH assumption in bilinear groups. The

(q, )-Poly-SDH is a parametric assumption that mildly generalizes the earlier

Strong Di¬e-Hellman assumption [8] in such groups. It can be stated as:

(Poly-SDH) Given g, g ±1 , ..., g ± ∈ G and q pairs (wi,j , g 1/(±i +wi,j ) ) for

1 ¤ i ¤ and 1 ¤ j ¤ q, choose a list of values w1 , ..., w ∈ Fp and output

pairs (wi , g ri /(±i +wi ) ) such that i=1 ri = 1.

2.2 Group Signatures

A group signature scheme involves a group manager, an opening manager, group

members and outsiders. The group manager is able to add new members by

issuing private keys thanks to a master key MK, while the opening manager can

use the tracing key TK to revoke the anonymity of any group signature.

Such a scheme is speci¬ed as a tuple GSS = (Setup, Join, Sign, Verify, Trace) of

algorithms described as follows:

“ The setup algorithm Setup generates, according to a security parameter, a

public veri¬cation key PK, a master key MK, and a tracing key TK.

“ The enrollment algorithm, Join, that generates a private signing key using

the master key MK. The private key is then given to the new user.

“ The group signing algorithm, Sign, that outputs a signature σ on a message

M , using a group member™s private key.

“ The (usually deterministic) group signature veri¬cation algorithm, Verify,

that takes as input the group veri¬cation key PK and a signature σ on a

message M , and outputs either valid or invalid.

“ The (usually deterministic) tracing algorithm, Trace, that takes a valid signa-

ture σ and a tracing key TK, and outputs the identity of a group member or ⊥.

The following correctness and security properties are required.

Expressive Subgroup Signatures 189

Consistency. Given a group signature generated by a honest group member, the

verify algorithm should output valid, and the tracing algorithm should identify

the actual signer.

Security. Bellare, Micciancio, and Warinschi [5] characterize the fundamental

properties of group signatures in terms of two crucial security properties from

which a number of other properties follow. The two important properties are

Full Anonymity and Full Traceability.

It is noted in [5] that the full traceability property implies that of exculpability

[4], which is the requirement that no party should be able to frame a honest group

member as the signer of a signature he did not make, not even the group manager.

However, the model of [5] does not consider the possibility of a (long-lived)

group master, which leaves it as a potential framer. To address this problem

and achieve the notion of strong exculpability, introduced in [2] and formalized

in [29,6], one also needs an interactive enrollment protocol, call Join, at the end

of which only the user himself knows his full private key; the same mechanism

may also enable concurrent dynamic group enrollment [6,29]. In this work, we

opt for this stronger notion and thus we shall explicitly describe such a Join

protocol.

We refer the reader mainly to [5] for more precise de¬nitions of these and

related notions.

2.3 Mesh Signatures

We now brie¬‚y recapitulate the notion of mesh signature introduced in [11].

In short, a mesh signature is a non-interactive witness-indistinguishable proof

that some monotone boolean expression Υ (L1 , . . . , Ln ) is true, where the input

literals Li denote the validity of “atomic signatures” of the form {Msgi }Keyi for

arbitrary messages and di¬erent keys. (The special case of ring signatures [30]

corresponds to Υ being a ¬‚at disjunction.)

Admissible mesh expressions Υ consist of trees of And, Or, and Threshold

gates, and single-use input literals, generated by the following grammar:

expr ::= L1 | ... | L single-use input symbols

| ≥t {expr1 , ..., exprm } t-out-of-m threshold, with 1 < t < m

| §{expr1 , ..., exprm } m-wise conjunction, with 1 < m

| ∨{expr1 , ..., exprm } m-wise disjunction, with 1 < m

Not all literals need to be true in order for Υ to be satis¬ed. However the

mesh signature must only attest to the truth of Υ without revealing how it is

satis¬ed: this is the anonymity property. Conversely, a signer should not be able

to create a mesh signature without possessing a valid atomic signature for every

literal set to true: this is the unforgeability property.

2.4 Security of Expressive Subgroup Signatures

ESS are just as expressive as mesh signatures, and provide the same anonymity,

except that the latter can be lifted by a tracing authority. We require:

190 X. Boyen and C. Delerabl´e

e

ESS Anonymity. The notion of anonymity we seek is not that we wish to

hide the identity of the users named in the ESS expression Υ (which is public

anyway), but to hide who among the users actually created the signature.

Precisely, we require that the identity of the actual signer(s) be computation-

ally indistinguishable in the set of all valid ESS signatures speci¬ed by the same

expression Υ , even under full exposure of all user keys. This is the same notion as

in the mesh signatures of [11], except that here the requirement is computational

and not information-theoretic in order not to stymie the tracing authority, and

is of course conditional on the secrecy of the tracing key.

ESS Traceability. Traceability is the group-signature version of unforgeability.

For ESS, as for mesh signatures before them, this notion is tricky to formalize

because of the potentially complex dependences that may exist between good

and forged signatures. To see this, consider a coalition of two forgers, U1 , U2 ,

and a honest user, U3 . Suppose that the forgers fabricate a valid ESS signature

σ for the expression Υ = {m1 }U1 ∨ ({m2 }U2 § {m3 }U3 ), that can be traced the

subgroup U2 , U3 . Is that a successful forgery? What if σ traced to U2 only?

The answer is a double “yes”: in the ¬rst case, because U3 was wrongly des-

ignated by the tracer; and in the second case, because U2 alone could not have

satis¬ed Υ , which means that some guilty party escaped detection. If on the

other hand, the ¬nger were pointed at U1 , the signature would have a satisfac-

tory explaination that involves only (the parties that we know to be) the culprits:

this would be a failed forgery since the coalition got caught.

The ESS traceability challenge is thus, for any coalition of signers, to come

up with a valid signature σ for an expression Υ (L1 , . . . , Ln ), such that σ, either,

traces to at least one user outside of the coalition, or, traces to a subset of the

coalition that does not validate Υ (that is, when Υ is “false” after setting the

designated literals Li to “true” and only those).

Strong Exculpability. This last notion is borrowed straight from group signa-

tures [2,29,6], and is orthogonal to the above. It gives any user the possibility to

dispute his alleged binding to any certi¬cate that he did not request. To defend

from such accusation, the group manager (who signed the disputed certi¬cate)

must produce a valid certi¬cate request signed by the user™s individual key reg-

istered in some PKI. The enrollment protocol must guarantee that only the user

learns the private key associated with their certi¬cates. Together, this prevents

the ESS group manager from framing users for signatures they did not make.

2.5 Formal Security Models

We now specify the formal ESS security model in accordance with the previously

stated requirements.

Anonymity. The ESS anonymity game is played between a challenger and an

adversary.

Initialization. The challenger gives to the adversary the public param-

eters of an ESS.