Interaction. The following occurs interactively, in any order, driven by

the adversary.

User enrollment. The adversary may ask the challenger to enroll

a polynomially bounded number of new users in the group. The

adversary may either impersonate the user in the enrollemnt pro-

tocol, or ask the challenger to simulate it all by itself. The re-

sulting public certi¬cates are published.

Signature queries. The adversary may ask the challenger to sign

any ESS expression Υ on behalf of the users it controls.

Key recovery. The adversary may ask the challenger to reveal the

group signing key of any user.

The challenger processes each request before accepting the next one.

Challenge: The adversary ¬nally output a speci¬cation Υ and two sets

of assignments χ1 and χ2 to its literals Li , that both cause Υ to be

satis¬ed. These truth assignments indicate which users are supposed

to sign Υ . The adversary must also supply the necessary atomic

signatures for the users for which it has the keys.

The challenger chooses one assignment b ∈ {1, 2} at random, and

creates an ESS signature σ on the speci¬cation Υ using only atomic

signatures corresponding to the true literals in χi . The signature σ

is given to the adversary.

Guess: The adversary makes a guess b , and wins the game if b = b .

The adversary™s advantage in the ESS anonymity game is Pr[b = b ] ’ 1/2, where

the probability is de¬ned over the random coins used by all the parties.

Traceability. The ESS traceability game is played between a challenger and an

adversary.

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

eters of an ESS. The challenger also reserves a number of user

indices to represent the “honest users” under its control.

Interaction. The following occurs interactively, in any order, driven by

the adversary.

Honest user enrollment. The adversary may request that the

challenger create up to honest users, kept in the challenger™s

control. The challenger publishes the corresponding certi¬cates.

Corrupted user enrollment. The adversary makes polynomially

user enrollment queries, for the users under the adversary™s con-

trol. The adversary chooses or receives the user secret keys in

accordance with the chosen enrollment protocol. The challenger

computes the corresponding certi¬cates in accordance with the

enrollment protocol, and publishes them.

ESS signature queries. The adversary makes up to q ESS signa-

ture queries, one at a time, on speci¬cations Υj , indicating to

the challenger which ones of the honest users are supposed to

issue the signature. To be acceptable, each request must be for

192 X. Boyen and C. Delerabl´e

e

a signature that the speci¬ed subset of honest users is supposed

to be able to make based on the speci¬cation and supporting

atomic signatures provided by the adversary.

The adversary may also make up to q queries for atomic signa-

tures, to each of the users controlled by the challenger.

The challenger processes each request before accepting the next one.

Forgery: The adversary ¬nally output a fresh valid ESS signature σ

for some speci¬cation Υ of its choice. It wins the game if the list of

literals Li designated by the tracing algorithm on input σ fails to

satisfy the two following properties:

1. All the designated literals Li correspond to atomic signatures

{Msgi }Useri under the adversary™s control (either because the

adversary controls the corresponding user, or had obtained the

atomic signature by querying the challenger).

2. The speci¬cation formula Υ (..., Li , ...) can be satis¬ed by setting

all the designated literals to “true” ( ) and all the other literals

to “false” (⊥).

The adversary™s advantage in the ESS traceability game is simply the probability

that it wins the game. The probability is de¬ned over the random coins used by

all the parties.

3 Construction

Our Expressive Subgroup Signature construction will bring together a number

of di¬erent techniques.

To get the anonymity properties we seek, we will naturally start with the

ring/mesh signatures from [11], which comes with a powerful language and proof

system. We use it to create an anonymous group identi¬cation mechanism for

certi¬cates issued by the group manager. Since we need a signature scheme and

not just an identi¬cation scheme, we shall extend the certi¬cates into certi¬cate

chains ending with actual signatures from users™ keys. This part is easy to do us-

ing the mesh language, so this step will be a simple matter of specifying how the

various terminal signatures and their supporting certi¬cates should be assem-

bled. This gives us a multi-user anonymous signature with a central authority.

However, we still lack traceability.

To get traceability, we need to build a trapdoor that will remove the blinding

from the mesh signatures. Recall that the ring and mesh signatures from [11] con-

sist of one signature element per ring or mesh member. Some of those elements

are “live”, meaning that they were created using the member™s actual secret key.

The remaining elements are “blank” and do not contribute to the veri¬cation

equation. Since it would be easy to tell who the signers were just by ¬nding the

live elements, the elements are information-theoretically blinded so that they all

look the same. Here, to get traceability, we shall swap out the perfect blinding

for one that has a trapdoor. Since the mesh signatures require a bilinear pairing

Expressive Subgroup Signatures 193

for their veri¬cation, we shall add the trapdoor into the bilinear group, using a

standard trick used in several previous constructions [22]. We simply translate

the signatures into a bilinear group of composite order, and restrict the blind-

ing elements to one of its two algebraic subgroups. An adversary will just see

smoke under the proper hardness assumption [10]; but a tracing authority that

knows the order of the subgroups will be able to cancel the blinding (by pairing

each signature component with a neutral element in that subgroup), and hence

distinguish which signature components are live and which ones are blank.

In the following subsections, we explain step-by-step how to construct expres-

sive subgroup signatures. We work in an algebraic group G of composite order

N = pq and equipped with a bilinear pairing e : G — G ’ GT . We call G the

bilinear group and GT the targer group; both are of order N . Bilinearity is the

property that ∀u, v ∈ G, ∀a, b ∈ Z, e(ua , v b ) = e(u, v)ab mod N .

3.1 User Credentials

Users must be a¬liated with the group in order to create signatures, which

means that they must have acquired proper credentials from the group manager

(which controls the user vetting and enrollment process).

In its most basic instantiation, a certi¬cate for user i could simply be a secret

key for the Boneh-Boyen signature scheme [8]. The secret key (yi , zi ) ∈ Z2 p

would be securely handed over to the user, and the corresponding public key

(g yi , g zi ) ∈ G2 signed by the group manager and perhaps published as part of the

group description. A signature on m ∈ Zp would be a random pair (t, S) ∈ Zp —G,

where S = g 1/(yi +m+zi t) , which is veri¬able by testing e(S, g yi g m g zi t ) = e(g, g).

The drawback is that the group manager would know yi and zi and would thus

be able to create signatures on the user™s behalf. We would also need to embed

a tracing trapdoor into all user-generated signatures.

In the preferred instantiation, a group certi¬cate will depend on a secret

component that is known only to the user, to prevent users from being framed.

It should also depend on a secret from the manager, to guarantee traceability.

Using a technique close to the one proposed by Delerabl´e and Pointcheval [19],

e

we let the credentials for user i consist of a secret key (xi , yi , zi ) and a public

certi¬cate (Ai , Bi , Ci ), where Ai = g yi/(γ+xi ) , Bi = g 1/(γ+xi ) , and Ci = g zi/(γ+xi ) ,

for some random xi . Here, γ and “ = hγ are respectively the secret and public

key of the group manager, and g and h are two ¬xed generators of the group G.

The certi¬cate of user i is the triple (Ai , Bi , Ci ) signed by the group manager.

For randomly chosen t ∈ Zp , an “atomic signature” on m ∈ Zp will be a pair:

1

σ = (t, S) ∈ Zp — G S = (“ hxi ) /(yi +m+zi t) .

s.t.

mt

The veri¬cation equation is thus: e(S, Ai Bi Ci ) = e(h, g).

For simplicity reasons, we can merely suppose a enrollment protocol where

the user chooses (yi , zi ), sends (g yi , g zi ) to the group manager along with a

proof of knowledge, and receives (xi , Ai , Bi , Ci ) in return. Nevertheless, following

194 X. Boyen and C. Delerabl´e

e

a technique from [19], in Section 3.7 we present a more complex “dynamic”