o a

Trans. on Information Theory 46, 2596“2605 (2000)

32. Rabin, M.O.: Randomized Byzantine generals. In: Proc. of the 24th IEEE Symp.

on Foundations of Computer Science, pp. 403“409 (1983)

33. Reingold, O.: Undirected ST-connectivity in log-space. In: Proc. of the 37th ACM

Symp. on the Theory of Computing, pp. 376“385 (2005)

34. R´nyai, L., Babai, L., Ganapathy, M.K.: On the number of zero-patterns of a

o

sequence of polynomials. Journal of the AMS 14(3), 717“735 (2001)

35. Shamir, A.: How to share a secret. Communications of the ACM 22, 612“613 (1979)

36. Simmons, G.J., Jackson, W., Martin, K.M.: The geometry of shared secret schemes.

Bulletin of the ICA 1, 71“88 (1991)

37. Stinson, D.R.: Decomposition construction for secret sharing schemes. IEEE Trans.

on Information Theory 40(1), 118“125 (1994)

38. Tardos, E.: The gap between monotone and non-monotone circuit complexity is

exponential. Combinatorica 8(1), 141“142 (1988)

Expressive Subgroup Signatures

Xavier Boyen1 and C´cile Delerabl´e2

e e

1

Voltage, Palo Alto, California

xb@boyen.org

2

Orange Labs - ENS

cecile.delerablee@orange-ftgroup.com

Abstract. In this work, we propose a new generalization of the notion

of group signatures, that allows signers to cover the entire spectrum

from complete disclosure to complete anonymity. Previous group signa-

ture 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 exactly in what capacity a subgroup of

signers is making a signature on behalf of the group.

1 Introduction

Collective signatures allow an individual to make a signed statement

anonymously on behalf of a coalition. Whereas ring signatures [30] are uncon-

ditionally anonymous, group signatures [17] come with an anti-abuse protec-

tion mechanism, whereby a tracing authority can lift a signature™s anonymity

to uncover the identity of the signer in case of necessity. In group signatures,

membership to the group must be restricted and subject to a formal vetting

and enrollment process of its members: these are desirable properties in many

applications.

In many contexts, the blunt anonymity provided by group signatures goes

too far, and it would be preferable to go half-way between full anonymity and

full disclosure ” e.g., to boost the credibility of a statement without completely

engaging the individual responsibility of the signer. This is especially important

in groups with many members, or with members of di¬ering competences, or

any time several signers wish to sign a joint statement while retaining some

anonymity within a larger group.

The “Ad Hoc Group Signatures” from [20] at Eurocrypt 2004 provided a

partial answer, by allowing a signer to disclose that he or she belongs to a

particular subset of the group, not just the entire group. The “Mesh Signatures”

from [11] at Eurocrypt 2007 went further by providing a very expressive language

that signer(s) could use to make very speci¬c statements as to the capacity in

which they created the signature (such as, “undersigned by, either, ¬ve senators,

or, two deputies and the prime minister”). Unfortunately mesh signatures were

a generalization of ring signatures with no provision for traceability.

In this work, we propose a group signature with a mesh-like expressive lan-

guage for proving and verifying complex propositions about group membership,

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 185“200, 2008.

c Springer-Verlag Berlin Heidelberg 2008

186 X. Boyen and C. Delerabl´e

e

including those whose ful¬llment requires credentials from more than one group

member. Given a valid signature, anyone can verify that it was created by a

subgroup of signers that satis¬ed a certain condition (stated as an expression

given with the signature), and learn nothing else. However, the tracing author-

ity is able to unblind the signature and ¬nd out exactly how the condition was

ful¬lled, and thus who the signers are.

The construction we propose is based primarily on the mesh signatures of [11],

which we modify in order to equip with a tracing capability. The tracing mecha-

nism is inspired by a number of recent group signature constructions [12,1,13,21],

which all made use of zero-knowledge proof systems in bilinear groups of com-

posite order [10,22,23]. Compared to those, however, the present work provides a

technical novelty: the composite algebraic group and the zero-knowledge proofs

had to be ¬‚ipped “inside out” in order to be compatible with the more expressive

language that we implement.

Our signatures are e¬cient, both in the asymptotic and the practical sense: the

signature size will be linear in the size of the expression that it represents, with

a small proportionality constant. Although it would surely be nice to shrink the

cryptographic part of the signature further down to a constant-size component,

this is not of great importance here since the total signature size and veri¬cation

time would still have to be linear or worse ” because the veri¬cation expression

has to be stated and used somewhere, and the access structure it represents is

likely to change from one signature to the next. (Contrast this with regular group

signatures, where it is more desirable to have signatures of constant size, because

the group composition is ¬xed and need not be repeated.) For comparison, our

¬ne-grained group signature is essentially as short and e¬cient as the mesh

signature of [11], which is the most relevant benchmark for it is the only known

anonymous signature that is as expressive as ours (albeit lacking the tracing

capability).

Our scheme satis¬es (suitable version of) the usual two main security prop-

erties of group signatures originally de¬ned in [5]. The two properties are here:

Full Anonymity for CPA-attacks [9] and Full Traceability with Dynamic Join

[6], from which other natural requirements such as existential unforgeability,

non-frameability, strong exculpability, collusion resistance, etc., can be shown

to follow (see [5,6]). We shall de¬ne the two core properties precisely as they

generalize to our more expressive notion of group signatures, and prove that

our scheme satis¬es them under previously analyzed complexity assumptions,

in the standard model (unless a join protocol is used for strongly exculpability,

in which case we need either random oracles or a common reference string to

realize extractable commitments).

The name “Expressive Subgroup Signatures” is meant to capture that at

the core these are group signatures, albeit not ones whose level of (revocable)

anonymity is ¬xed and depends only on the group composition, but can be

adjusted “in the ¬eld” with great precision, any time a new signature is created

by any subgroup of signer(s) within the group boundaries.

Expressive Subgroup Signatures 187

1.1 Related Work

Ring signatures. Ring signatures were introduced in [30]. Each user in the system

has a public key, and can generate a ring signature. Such a signature implicates

some other users, chosen by the signer, and is such that a veri¬er is convinced

that someone in the ring formed by the public keys of the signer and the chosen

members is responsible for the signature, but nothing else. Constant-size ring

signatures were constructed in [20]. Recently, a number of ring signatures without

random oracles have been constructed from pairings, such as [18,7,31,11].

Mesh signatures. Mesh signatures were recently proposed [11] as a powerful gen-

eralization of ring signatures, with a rich language for striking the desired balance

from full disclosure to full anonymity and almost anything in between (including

complex statements involving, inter alia, trees of conjunctions and disjunctions

of multiple potential signers). The work of [11] gave the ¬rst unconditionally

anonymous ring signatures without random oracles as a special case.

Group signatures. Group signatures were ¬rst proposed in [17] to allow any

member of a speci¬c group to sign a message on behalf of the group, while

keeping the signer anonymous within the group. However, a tracing authority

has the ability to uncover the identity of the signer, which it should only do

in certain extenuating circumstances. Group signatures have attracted much

attention in the research community; we mention for example the works of

[1,2,3,5,6,9,12,13,14,15,16,27,29,32].

For completeness, we mention the recently proposed notion of “attribute-

based group signature” [26,25], which, contrarily to what the name might sug-

gest, is a far cry from ful¬lling our goal. (These signatures are rather in¬‚exible,

as they require that the attribute trees be constructed by the setup authority,

and not the signer. Furthermore, verifying each attribute tree requires a di¬erent

public key which must be requested interactively from the setup authority.)

2 Preliminaries

2.1 Composite-Order Pairings