and provides strong user exculpability [6] against dishonest managers.

3.2 Atomic Signatures

Using their credentials, users are able to create atomic signatures on any message

of their choice, which for simplicity we assume represented as an integer m ∈ Zp .

Atomic signatures provide no anonymity; they merely serve as building blocks

in more complex assemblies.

An atomic signature created from credentials as above is a pair (t, S) ∈ Zp —G

that satis¬es a veri¬cation equation of the form,

mt

e(S, Ai Bi Ci ) = e(h, g) ,

R

with respect to a publicly veri¬able certi¬cate (Ai , Bi , Ci ) associated to user i.

We observe for later use that this is exactly a Boneh-Boyen signature, and that

the right-hand side e(h, g) in the veri¬cation equation is the same for all users.

3.3 Ring Signatures

Once we have atomic signatures of the previous form, we can easily construct an

information-theoretically anonymous ring signature, based on the approach pro-

posed in [11]. Suppose that there are n users with public certi¬cates (A1 , B1 , C1 )

through (An , Bn , Cn ), and consider the following veri¬cation equation for some

message m, or more generally, for respective user messages m1 through mn :

n

m t

e(Si , Ai Bi i Ci i ) = e(h, g) .

i=1

Ri

Any one of the n users is able to create, by himself, a vector of n pseudo-

signatures (ti , Si ) for i = 1, . . . , n that will jointly verify the preceding equation.

In order to do so, the user will need his own key and everyone else™s certi¬cates.

For example, user 1 would pick random r2 , . . . , rn , and t1 , . . . , tn , and set:

n

’r ’r

1/(y +m +z t )

· r

x1

Ri i , S2 = R1 2 , Sn = R1 n .

1 1 11

S1 = (“ h ) ... ,

i=2

It is easy to see that, for any random choice of ri ∈ Zp , the blinding terms

in the square brackets will cancel each other in the product of pairings in the

’r

r

veri¬cation equation; e.g., e(R22 , R1 ) from S1 will cancel e(R1 2 , R2 ) from S2 .

1

What is left is the Boneh-Boyen signature component (“ hx1 ) /(y1 +m1 +z1 t1 ) in S1 ,

which in the veri¬cation equation will produce the value e(h, g) we seek.

Expressive Subgroup Signatures 195

For the example of user 1 being the actual signer, the cancellation that occurs

is, in extenso, if we let S1 = (“ hx1 )1/(y1 +m1 +z1 t1 ) :

n n n

e(Si , Ri ) = e(S1 , R1 ) · e( ·

r

Ri i , R1 ) e(Si , Ri )

i=1 i=2 i=2

n n

’r

= e(S1 , R1 ) · e( Ri i , R1 ) ·

r

e(R1 i , Ri )

i=2 i=2

n n

e(R1 , Ri )’ri

= e(h, g) · e(Ri , R1 )ri · = e(g, h)

i=2 i=2

The point is that user 2 (or any other user j) could have achieved the same

result by using his own secret key inside S2 (or Sj ), but nobody else could,

without one of the users™ key. Also, because there are 2n components in the

signature, but 2n ’ 1 randomization parameters and 1 perfectly symmetric

veri¬cation equation, it is easy to see that the joint distribution of the full

signature (ti , Si )n is the same regardless of which one of the n listed users

i=1

created it.

Hence, this is a ring signature, i.e., a witness-indistinguishable proof for the

disjunction “{m1 }user1 ∨ {m2 }user2 ∨ . . . ∨ {mn }usern ”. The signature can be

shown to be unconditionally anonymous, and existentially unforgeable under the

n-Poly-SDH assumption [11], which slightly generalizes the SDH assumption [9].

3.4 Mesh Signatures

The next step is to turn those ring signatures into something that is much more

expressive. Recall that ring signatures can be viewed as witness-indistinguishable

“disjunctions” of individual signatures. Since the disjunction L1 ∨ L2 ∨ . . . ∨ Ln is

the least restrictive of all (non-trivial) propositional expressions over L1 , . . . , Ln ,

it should be possible to express di¬erent statements by adding more constraints

to the signature. E.g., we could require that supplemental veri¬cation equa-

tions be satis¬ed conjointly. The “mesh signatures” of [11] are based on this

principle.

A classic result from [24] shows that any monotone propositional expression

over a set of literals can be represented e¬ciently and deterministically using

a system of linear equations { n »i,j νi = »j }k+1 over the same number of

j=1

i=1

variables: a literal Li will be true in a true assignment if and only if the corre-

sponding variable νi has a non-zero value in the corresponding system solution

(of which there may be many).

In the construction of [11], the linear system coe¬cients »i,j will become

public exponents in the veri¬cation equations. Depending on the expression it

represents, a mesh signature (ti , Si )n requires 1 ¤ k + 1 ¤ n veri¬cation

i=1

m t

equations (with the usual Ri = Ai Bi i Ci i computable from public values):

196 X. Boyen and C. Delerabl´e

e

n

e(Si , Ri ) = e(h, g) ,

i=1

n

e(Si , Ri )»i,1 = 1 ,

i=1

...

n

e(Si , Ri )»i,k = 1 .

i=1

To make a signature, the signer, or coalition of signers, must prove that the

propositional expression has a solution, i.e., that there is a vector of Si that

1

passes all the equations. This can be done by setting Si ← ((“ hxi ) /(y1 +mi +z1 t1 ) )νi

given any solution vector (ν1 , . . . , νn ) of the linear system. However, for every

index i with a non-zero solution νi = 0, the signer(s) will be unable to create Si

1

unless they possess or are able to create the atomic signature (“ hxi ) /(y1 +m+z1 t1 ) .

Only for νi = 0 can they get by without it.

This procedure results in a valid signature, but not in an anonymous one. The

last step is thus to hide the witness, i.e., the vector (ν1 , . . . , νn ) used to build the

Si . This is done by adding blinding terms to the Si just as in the ring signature.

The result is an unconditionally anonymous signature for arbitrary monotone

propositional expressions.

The entire mesh signing process and its security proofs are somewhat more

involved. Full mesh signatures also require a presence of a dummy user “in the

sky” (with a public random public key and no known secret key), who will “sign”

a hash of the entire mesh expression in order to “seal” it. We refer the reader to

[11] for details.

3.5 Tracing Trapdoor

We now have an expressive anonymous signature, albeit not a traceable one. To

make mesh signatures traceable, we need to rede¬ne the mesh signature scheme

in bilinear groups of composite order N . The factorization N = pq is a trapdoor