17. Chaum, D., van Heyst, E.: Group signatures. In: Davies, D.W. (ed.) EUROCRYPT

1991. LNCS, vol. 547, pp. 257“265. Springer, Heidelberg (1991)

200 X. Boyen and C. Delerabl´e

e

18. Chow, S.M., Wei, V.K.-W., Liu, J.K., Yuen, T.H.: Ring signatures without random

oracles. In: ASIACCS 2006 Conference on Computer and Communications Security,

Taipei, Taiwan, pp. 297“302. ACM Press, New York (2006)

19. Delerabl´e, C., Pointcheval, D.: Dynamic fully anonymous short group signatures.

e

In: Nguyˆn, P.Q. (ed.) VIETCRYPT 2006. LNCS, vol. 4341, pp. 193“210. Springer,

e

Heidelberg (2006)

20. Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: Anonymous identi¬cation in ad hoc

groups. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027,

pp. 609“626. Springer, Heidelberg (2004)

21. Groth, J.: Fully anonymous group signatures without random oracles. In: Kuro-

sawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 164“180. Springer, Hei-

delberg (2007)

22. Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP.

In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339“358. Springer,

Heidelberg (2006)

23. Groth, J., Sahai, A.: E¬cient non-interactive proof systems for bilinear groups.

Cryptology ePrint Archive, Report 2007/155 (2007), http://eprint.iacr.org/

24. Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of Structures in

Complexity Theory, pp. 102“111 (1993)

25. Khader, D.: Attribute based group signature with revocation. Cryptology ePrint

Archive, Report 2007/241 (2007), http://eprint.iacr.org/

26. Khader, D.: Attribute based group signatures. Cryptology ePrint Archive, Report

2007/159 (2007), http://eprint.iacr.org/

27. Kiayias, A., Yung, M.: Extracting group signatures from traitor tracing schemes.

In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 630“648. Springer,

Heidelberg (2003)

28. Kiayias, A., Yung, M.: Group signatures: Provable security, e¬cient construc-

tions and anonymity from trapdoor-holders. Cryptology ePrint Archive, Report

2004/076 (2004), http://eprint.iacr.org/

29. Kiayias, A., Yung, M.: Group signatures with e¬cient concurrent join. In: Cramer,

R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 198“214. Springer, Heidelberg

(2005)

30. Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: Boyd, C. (ed.)

ASIACRYPT 2001. LNCS, vol. 2248, pp. 552“565. Springer, Heidelberg (2001)

31. Shacham, H., Waters, B.: E¬cient ring signatures without random oracles. In:

Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 166“180. Springer,

Heidelberg (2007)

32. Song, D.X.: Practical forward secure group signature schemes. In: ACM CCS 2001

8th Conference on Computer and Communications Security, Philadelphia, PA,

USA, November 5“8, 2001, pp. 225“234. ACM Press, New York (2001)

Anonymous Proxy Signatures

Georg Fuchsbauer and David Pointcheval

´

Ecole normale sup´rieure, LIENS - CNRS - INRIA, Paris, France

e

http://www.di.ens.fr/{˜fuchsbau,˜pointche}

Abstract. We de¬ne a general model for consecutive delegations of sign-

ing rights with the following properties: The delegatee actually signing

and all intermediate delegators remain anonymous. As for group signa-

tures, in case of misuse, a special authority can open signatures to reveal

the chain of delegations and the signer™s identity. The scheme satis¬es a

strong notion of non-frameability generalizing the one for dynamic group

signatures. We give formal de¬nitions of security and show them to be

satis¬able by constructing an instantiation proven secure under general

assumptions in the standard model. Our primitive is a proper generaliza-

tion of both group signatures and proxy signatures and can be regarded

as non-frameable dynamic hierarchical group signatures.

1 Introduction

The concept of delegating signing rights for digital signatures is a well studied

subject in cryptography. The most basic concept is that of proxy signatures, in-

troduced by Mambo et al. [MUO96] and group signatures, introduced by Chaum

and van Heyst [CvH91]. In the ¬rst, a delegator transfers the right to sign on

his behalf to a proxy signer in a delegation protocol. Now the latter can produce

proxy signatures that are veri¬able under the delegator™s public key. Security of

such a scheme amounts to unforgeability of proxy signatures, in that an adver-

sary cannot create a signature without having been delegated, nor impersonate

an honest proxy signer.

On the other hand, in a group signature scheme, an authority called the

issuer distributes signing keys to group members, who can then sign on behalf

of the group, which can be viewed as delegating the group™s signing rights to

its members”there is one single group signature veri¬cation key. The central

feature is anonymity, meaning that from a signature one cannot tell which one

of the group members actually signed. In contrast to ring signatures [RST01],

to preclude misuse, there is another authority holding an opening key by which

anonymity of the signer can be revoked. Generally, one distinguishes static and

dynamic groups, depending on whether the system and the group of signers

are set up once and for all or members can join dynamically. For the dynamic

case, a strong security notion called non-frameability is conceivable: Nobody”

not even the issuer nor the opener”is able to produce a signature that opens to

a member who did not sign. The two other requirements are traceability (every

valid signature can be traced to its signer) and anonymity, that is, no one except

the opener can distinguish signatures of di¬erent users.

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

c Springer-Verlag Berlin Heidelberg 2008

202 G. Fuchsbauer and D. Pointcheval

It is of central interest in cryptography to provide formal de¬nitions of primi-

tives and rigorously de¬ne the notions of security they should achieve. Only then

can one prove instantiations of the primitive to be secure. Security of group sig-

natures was ¬rst formalized by Bellare et al. [BMW03] and then extended to

dynamic groups in [BSZ05]. The model of proxy signatures and their security

were formalized by Boldyreva et al. [BPW03].1

The main result of this paper is to unify the two above-mentioned seemingly

rather di¬erent concepts, establishing a general model which encompasses proxy

and group signatures. We give security notions which imply the formal ones for

both primitives. Moreover, we consider consecutive delegations where all del-

egators (except the ¬rst of course) remain anonymous. As for dynamic group

signatures, we de¬ne an opening authority separated from the issuer and which

in addition might even be di¬erent for each user (for proxy signatures, a plausible

setting would be to enable the users to open signatures on their behalf). We call

our primitive anonymous proxy signatures, a term that already appeared in the

literature (see e.g. [SK02])”however without providing a rigorous de¬nition nor

security proofs. As it is natural for proxy signatures, we consider a dynamic set-

ting allowing to de¬ne non-frameability which we extend to additionally protect

against wrongful accusation of delegation.

The most prominent example of a proxy signature scheme is “delegation-by-

certi¬cate”: The delegator signs a document called the warrant containing the

public key of the proxy and passes it to the latter. A proxy signature then consists

of a regular signature by the proxy on the message and the signed warrant which

together can by veri¬ed using the delegator™s veri¬cation key only. Although not

adaptable to the anonymous case”after all, the warrant contains the proxy™s

public key”, a virtue of the scheme is the fact that the delegator can restrict

the delegated rights to speci¬c tasks speci¬ed in the warrant. Since our model

supports re-delegation, it is conceivable that a user wishes to re-delegate only a

reduced subset of tasks she has been delegated for. We represent tasks by natural

numbers and allow delegations for arbitrary sets of them, whereas re-delegation

can be done for any subsets.

The primary practical motivation for the new primitive is GRID Computing,

where Alice, after authenticating herself, starts a process. Once disconnected, the

process may remain active, launch sub-processes and need additional resources

that require further authentication. Alice thus delegates her rights to the process.

On the one hand, not trusting the environment, she will not want to delegate all

her rights, which can be realized by delegation-by-certi¬cate. On the other hand,

there is no need for the resources to know that it was not actually Alice who was

authenticated, which is practically achieved solely by full delegation, i.e., giving

the private key to the delegatee. While the ¬rst solution exposes the proxy™s

identity, the second approach does not allow for restriction of delegated rights

1

Their scheme has later been attacked by [TL04]. Note, however, that our de¬nition

of non-frameability prevents this attack, since an adversary querying PSig(·, warr, ·)

and then creating a signature for task is considered successful (cf. Sect. 3.3).

Anonymous Proxy Signatures 203

nor provide any means to trace malicious signers. Anonymous proxy signatures