An extended abstract of this paper appears in Advances in Cryptology – EUROCRYPT ’03, Lecture Notes in Computer Science Vol. 2656 , E. Biham ed., Springer-Verlag, 2003. This is the full version.
Foundations of Group Signatures:
Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions
Mihir Bellare∗ Daniele Micciancio† Bogdan Warinschi‡ May 2003
Department of Computer Science and Engineering, University of California, San Diego
9500 Gilman Drive, CA 92093
{mihir,daniele,bogdan}@cs.ucsd.edu
Abstract
This paper provides theoretical foundations for the group signature primitive. We introduce strong, formal definitions for the core requirements of anonymity and traceability. We then show that these imply the large set of sometimes ambiguous existing informal requirements in the literature, thereby unifying and simplifying the requirements for this primitive. Finally we prove the existence of a construct meeting our definitions based only on the assumption that trapdoor permutations exist.
Keywords: Foundations, theory, definitions, trapdoor permutations, group-signature schemes, anonymity.
∗Supported in part by NSF grant CCR-0098123, NSF grant ANR-0129617 and an IBM Faculty Partnership Development Award.
†Supported in part by NSF CAREER Award CCR-0093029. ‡Supported in part by NSF CAREER Award CCR-0093029.
Contents
1 Introduction 3
1.1 Background......................................... 3 1.2 Formaldefinitions ..................................... 3 1.3 Implications......................................... 4 1.4 Ourscheme......................................... 5 1.5 Relatedwork ........................................ 5
2 Definitions of the security of group signature schemes 6
3 Relations to Existing Security Notions 9
4 Our construction 10
4.1 Primitives.......................................... 10 4.2 Ourconstruction ...................................... 13 4.3 SecurityResults....................................... 14
5 Dynamic Groups and Other Extensions 23
1 Introduction
A central line of work in theoretical cryptography is to provide formal (and strong) definitions of se- curity for cryptographic primitives, and then provide constructions, based on general computational- complexity assumptions (such as the existence of one-way or trapdoor functions), that satisfy the definitions in question. The value and difficulty of such “foundational” work is acknowledged and manifest. A classical example is public-key encryption. Although it might seem like an intuitive goal, much work has been required to formally define and provably achieve it [20, 22, 19, 23, 26, 17], and these advances now serve as the basis for new schemes and applications. This paper provides such foundations for the group signatures primitive.
1.1 Background
In the group signature setting introduced by Chaum and Van Heyst [14] there is a group having numerous members and a single manager. Associated to the group is a single signature-verification key gpk called the group public key. Each group member i has its own secret signing key based on which it can produce a signature relative to gpk. The core requirements as per [14] are that the group manager has a secret key gmsk based on which it can, given a signature σ, extract the identity of the group member who created σ (traceability) and on the other hand an entity not holding gmsk should be unable, given a signature σ, to extract the identity of the group member who created σ (anonymity).
Since [14], more requirements, that refine or augment the core ones, have been introduced (eg. unlinkability, unforgeability, collusion resistance [5], exculpability [5], and framing resistance [15]) so that now we have a large set of unformalized, overlapping requirements whose precise meaning, and relation to each other, is neither always clear nor even always agreed upon in the existing literature.
The state of the art is represented by [5, 2] that identify weaknesses in previous works and present new schemes. The schemes in [2] are claimed to be proven-secure (in the random oracle model). However, while the work in question establishes certain properties, such as zero-knowledge, of certain subprotocols of its scheme, there is no actual definition of the security of a group signature scheme. For example, the anonymity requirement is formulated simply as the phrase “given a valid signature of some message, identifying the actual signer is computationally hard for everyone but the group manager.” This is like formulating the privacy requirement for an encryption scheme as the phrase “the ciphertext should not reveal information about the message to anyone except the owner of the secret key,” yet to truly capture privacy requires significantly more precise and non- trivial definitions, as evidenced by [20, 22, 19, 23, 26, 17]. In particular the informal requirement of [2] leaves open the issue of what exactly is the attack model and definition of adversarial success. Can the attacker see, or request, previous signatures? Can it call on the group manager to “open” some previous signatures? Can it have partial information ruling out some signers a priori? With such questions unanswered, we believe it is premature to say that proven-security has been achieved.
Furthermore, all claims of proven secure schemes so far have been in the random-oracle model. As far as we know, there are no constructions even claimed to be proven secure in the standard model.
1.2 Formal definitions
Providing appropriate definitions has required significantly more than merely formalizing the in- tuitive informal requirements of previous works. We consider novel attack capabilities and success
measures, and then formulate strong versions of the core requirements that we call full-anonymity and full-traceability. Perhaps surprisingly, we are then able to show that these two requirements are enough, in the sense that all the other requirements are implied by them. Our formalisms build on definitional ideas used for encryption [20, 22, 19, 23, 26, 17] and digital signatures [21].
Full-anonymity. We adopt an indistinguishability based formalization under which the adver- sary produces a message and a pair of group-member identities, is returned a target signature of the given message under a random one of the two identities and then is required to have negligible advantage over one-half in determining under which of the two identities the target signature was produced. Within this framework, we define a strong adversary that may corrupt all the members of the group, including the one issuing the signature. (Formally, the adversary is given the secret keys of all group members.) We also capture (in analogy to the definition of encryption secure against chosen-ciphertext attack [26]) the possibility that the adversary can see the outcome of opening attempts conducted by the group manager on arbitrary signatures of its choice (except of course the challenge signature).
Full-traceability. Our formulation of traceability is much stronger than what was called trace- ability in the past, and can be viewed also as a strong form of collusion-resistance. It asks that a group of colluding group members who pool their secret keys cannot create a valid signature that the opening algorithm would not catch as belonging to some member of the colluding group, and this is true even if the colluding group knows the secret key of the group manager under which signatures are opened.
1.3 Implications
As indicated above, there is a large and growing list of informal security requirements for group signatures. We show however that all existing requirements are implied by full-anonymity plus full- traceability. This provides a conceptual simplification with a clear advantage: having to check only two security properties makes it easier to give formal proofs of security when new group signature schemes are invented.
These implications might seem surprising at first glance, particularly because the implied prop- erties include seemingly unrelated notions like unforgeability (nobody outside the group can pro- duce valid signatures) or security against framing attacks (no one can produce signatures that will be later attributed to a honest group member that never signed the corresponding document). However the fact that a small number of strong formal notions imply a large number of informal requirements should be viewed, based on historical evidence, as an expected rather than a surpris- ing benefit, and even as a test of the definitions in question. As an analogy, in the absence of a strong formal notion, one might formulate the security of encryption via a list of requirements, for example security against key-recovery (it should be hard to recover the secret key from the public key), security against inversion (it should be hard to recover the plaintext from the ciphertext), security under repetition (it should be hard to tell whether the messages corresponding to two ciphertexts are the same) and so on, and we can imagine these requirements being discovered in- crementally and being thought to be quite different from each other. However, strong notions like indistinguishability [20], semantic security [20] and non-malleability [17] imply not only all these, but much stronger properties, and in particular put the different informal requirements under a common umbrella. We believe we are doing the same for group signatures.
1.4 Our scheme
With such strong notions of security, a basic theoretical question emerges, namely whether or not a scheme satisfying them even exists, and, if so, what are the minimal computational-complexity assumptions under which this existence can be proven. We answer this by providing a construction of a group signature scheme that provably achieves full-anonymity and full-traceability (and thus, by the above, also meets all previous security requirements) assuming only the existence of trapdoor permutations. We stress that this result is not in the random oracle model. Additionally we note that our construction is “non-trivial” in the sense that the sizes of all keys depend only logarithmically (rather than polynomially) on the number of group members.
The construction uses as building blocks an IND-CCA secure asymmetric encryption scheme, known to exist given trapdoor permutations via [17]; simulation-sound adaptive non-interactive zero-knowledge (NIZK) proofs for NP, known to exist given trapdoor permutations via [18, 28]; and a digital signature scheme secure against chosen-message attack, known to exist given trapdoor permutations via [6]. As often the case with constructs based on general assumptions, our scheme is polynomial-time but not practical, and our result should be regarded as a plausibility one only.
The basic framework of our construction builds on ideas from previous works (eg. [2]). Roughly, the secret signing key of a group member includes a key-pair for a standard digital signature scheme that is certified by the group manager. The group member’s signature is an encryption, under a public encryption key held by the group manager, of a standard signature of the message together with certificate and identity information, and accompanied by a non-interactive zero-knowledge proof that encryption contains what it should.
Previous works did not try to achieve security notions as strong as we target, nor to pin down what properties of the building blocks suffice to actually prove security. For example we found that the encryption scheme had to be secure against chosen-ciphertext attack and not just chosen- plaintext attack. Further subtleties are present regarding the NIZK proofs. We require them to be simulation-sound and also have a strong, adaptive zero-knowledge property [28]. On the other hand, we only require NIZK proofs for a single theorem rather than multiple theorems. We highlight this because at first glance it can sound impossible, but it is due to the strong ZK property, and the situation is not without precedent: single-theorem adaptive ZK proofs have sufficed also for applications in [28].
1.5 Related work
As indicated above, the notion of group signature was introduced by Chaum and Heyst in [14]. They also gave the first schemes. Since then, many other schemes were proposed, including [15, 11, 25, 13, 4]. These schemes improve on the performance of the original group signature scheme of [14], but leave open some important security issues, most notably security against coalitions of group members. The importance of achieving provable security against coalitions of group members is pointed out in [5], where a (partial) coalition attack on the scheme of [13] is also described. A subsequent work trying to address the issue of securing group signature schemes against coalition attacks is [2]. On a separate research line, [10, 3, 12] investigate issues related to the dynamics of the group, to support membership revocation, and independent generation of group member keys. Still another extension is that of [29], that combines group signature schemes with forward security [1, 7].
The definitions and results of this paper are for the setting in which the group is static, meaning the number and identities of members is decided at the time the group is set up and new members cannot be added later. We consider it important to begin with this setting because, even though
dynamic groups have been considered (as indicated above), proper definitions of security have not been provided even for the basic static-group case, and the important definitional issues arise already in this context.
Our work provides a basis from which to treat the case of dynamic groups, but the latter do give rise to new issues. Section 5 discusses dynamic groups and other extensions. Providing formal definitions of security and provably-secure constructions for dynamic group signatures is the subject of on-going work [8].
2 Definitions of the security of group signature schemes
Notation and terminology. If x is a string, then |x| denotes its length, while if S is a set then |S| denotes its size. The empty string is denoted by ε. If k ∈ N then 1k denotes the string of k ones. If n is an integer then [n] = {1,...,n}. If A is a randomized algorithm then z ←$ A(x,y,...) denotes the operation of running A on inputs x,y,... and letting z be the output. If A is a randomized algorithm then [A(x, y, . . .)] denotes the set of all points having positive probability of being output by A on inputs x,y,....
We say that a function f: N → N is nice if it is polynomially bounded (i.e. there exists a polynomial p(·) such that f(k) ≤ p(k) for all k ∈ N) and computable in poly(k) time. The notion of a function ν: N → N being negligible is standard. In this paper we will need a notion of negligibility of a two-argument function μ: N × N → N. We say such a μ is negligible if for every nice function n: N → N, the function μn: N → N is negligible, where μn(k) = μ(k,n(k)) for all k ∈ N.
Syntax of group signature schemes. A group signature scheme GS = (GKg, GSig, GVf, Open) consists of four polynomial-time algorithms:
• The randomized group key generation algorithm GKg takes input 1k,1n, where k ∈ N is the security parameter and n ∈ N is the group size (ie. the number of members of the group), and returns a tuple (gpk, gmsk, gsk), where gpk is the group public key, gmsk is the group manager’s secret key, and gsk is an n-vector of keys with gsk[i] being a secret signing key for player i ∈ [n].
• The randomized group signing algorithm GSig takes as input a secret signing key gsk[i] and a message m to return a signature of m under gsk[i] (i ∈ [n]).
• The deterministic group signature verification algorithm GVf takes as input the group public key gpk, a message m, and a candidate signature σ for m to return either 1 or 0.
• The deterministic opening algorithm Open takes as input the group manager secret key gmsk, a message m, and a signature σ of m to return an identity i or the symbol ⊥ to indicate failure.
For simplicity we are assigning the members consecutive integer identities 1, 2, . . . , n. We say that σ is a true signature of m if there exists i ∈ [n] such that σ ∈ [GSig(gsk[i], m)]. We say that σ is a valid signature of m with respect to gpk if GVf(gpk, m, σ) = 1.
Correctness. The scheme must satisfy the following correctness requirement: For all k, n ∈ N, all (gpk, gmsk, gsk) ∈ [GKg(1k, 1n)], all i ∈ [n] and all m ∈ {0, 1}∗
GVf(gpk, m, GSig(gsk[i], m)) = 1 and Open(gmsk, m, GSig(gsk[i], m)) = i .
The first says that true signatures are always valid. The second asks that the opening algorithm
correctly recovers the identity of the signer from a true signature.
Discussion. The definitions above are for the setting in which the group is static, meaning the number and identities of members is decided at the time the group is set up and new members cannot be added later. For information about the dynamic group case refer to Section 5 and [8].
Experiment Expanon-b(k, n) GS,A
(gpk, gmsk, gsk) ←$ GKg(1k, 1n)
(St, i0, i1, m) ←$ AOpen(gmsk,·,·)(choose, gpk, gsk) ; σ ←$ GSig(gsk[ib], m)
d ←$ AOpen(gmsk,·,·)(guess, St, σ)
If A did not query its oracle with m, σ in the guess stage then return d EndIf Return 0
Experiment Exptrace (k, n) GS,A
(gpk, gmsk, gsk) ←$ GKg(1k, 1n)
St ← (gmsk, gpk) ; C ← ∅ ; K ← ε ; Cont ← true While (Cont = true) do
(Cont, St, j) ←$ AGSig(gsk[·],·)(choose, St, K)
If Cont = true then C ← C ∪ {j} ; K ← gsk[j] EndIf Endwhile
(m, σ) ←$ AGSig(gsk[·],·)(guess, St)
If GVf(gpk, m, σ) = 0 then return 0 ; If Open(gmsk, m, σ) = ⊥ return 1
If there exists i ∈ [n] such that the following are true then return 1 else return 0:
1. Open(gmsk, m, σ) = i
2. i̸∈C
3. i, m was not queried by A to its oracle
Figure 1:
signature scheme GS = (GKg, GSig, GVf, Open). Here A is an adversary, b ∈ {0, 1}, and St denotes state information passed by the adversary between stages.
Compactness. In practice it is preferable that sizes of keys and signatures in a group signature scheme do not grow proportionally to the number of members n. Actually, a polynomial dependency of these sizes on log(n) can be shown to be unavoidable, but ideally one would not want more than that. In our context, this leads to the following efficiency criterion for a group signature scheme. We call a group signature scheme GS = (GKg, GSig, GVf, Open) compact if there exist polynomials p1(·, ·) and p2(·, ·, ·) such that
|gpk|, |gmsk|, |gsk[i]| ≤ p1(k, log(n)) and |σ| ≤ p2(k, log(n), |m|)
for all k,n ∈ N, all (gpk,gmsk,gsk) ∈ [GKg(1k,1n)], all i ∈ [n], all m ∈ {0,1}∗ and all σ ∈
[GSig(gsk[i], m)].
Full-anonymity. Informally, anonymity requires that an adversary not in possession of the group manager’s secret key find it hard to recover the identity of the signer from its signature. As discussed in the introduction, our formalization is underlain by an indistinguishability requirement, on which is superimposed an adversary with strong attack capabilities. To capture the possibility of an adversary colluding with group members we give it the secret keys of all group members. To capture the possibility of its seeing the results of previous openings by the group manager, we give it access to an opening oracle, Open(gmsk,·,·), which when queried with a message m and signature σ, answers with Open(gmsk, m, σ).
Experiments used, respectively, to define full-anonymity and full-traceability of group
Let us now proceed to the formalization. To any group signature scheme GS = (GKg,GSig, GVf,Open), adversary A and bit b we associate the first experiment given in Figure 1. Here, A is an adversary that functions in two stages, a choose stage and a guess stage. In the choose stage A takes as input the group members secret keys, gsk, together with the group public key gpk. During this stage, it can also query the opening oracle Open(gmsk,·) on group signatures of his choice, and it is required that at the end of the stage A outputs two valid identities 1 ≤ i0, i1 ≤ n, and a message m. The adversary also outputs some state information to be used in the second stage of the attack. In the second stage, the adversary is given the state information, and a signature on m produced using the secret key of one of the two users i0, i1, chosen at random. The goal is to guess which of the two secret keys was used. The adversary can still query the opening oracle, but not on the challenge signature. We denote by
Advanon(k,n) = Pr?Expanon-1(k,n)=1?−Pr?Expanon-0(k,n)=1? GS,A GS,A GS,A
the advantage of adversary A in breaking the full-anonymity of GS. We say that a group signature
scheme is fully-anonymous if for any polynomial-time adversary A, the two-argument function
Advanon (·, ·) is negligible in the sense of negligibility of two-argument functions defined at the GS,A
beginning of this section.
In the above experiment, the adversary issues a request to sign its message m under one of two
identities i0,i1 that it specifies, and wins if it can guess which was chosen. One might feel that allowing just one such request is restrictive, and the adversary should be allowed a sequence of such requests. (The challenge bit b remains the same in answering all requests). However, a standard hybrid argument shows that, under polynomial-time reductions, allowing a polynomial number of requests is equivalent to allowing just one request, so our definition is not restrictive. This hybrid argument depends on the fact that the adversary has the group public key and the secret signing keys of all members.
Full-traceability. In case of misuse, signer anonymity can be revoked by the group manager. In order for this to be an effective deterrence mechanism, we require that no colluding set S of group members (even consisting of the entire group, and even being in possession of the secret key for opening signatures) can create signatures that cannot be opened, or signatures that cannot be traced back to some member of the coalition. We remark that giving the opening key to the adversary does not model corruption of the group manager,1 but rather compromise of the group manager’s key by the adversary. We call our requirement full-traceability.
We formally define full-traceability using the second experiment of Figure 1. Here, adversary A runs in two stages, a choose stage and a guess stage. On input the group public key gpk and the secret of the group manager, gmsk, the adversary starts its attack by adaptively corrupting a set C of group members. The identity of the group members that are corrupted and their number is entirely up to it. At the end of the choose stage the set C contains the identities of the corrupted members. In the guess stage, the adversary attempts to produce a forgery (m, σ), and we say it wins (meaning the experiment returns 1), if σ is a valid group signature on m, but the opening algorithm returns ⊥ or some valid user identity i such that i ̸∈ C. Otherwise, the experiment returns 0. We define the advantage of adversary A in defeating full-traceability of the group signature scheme GS by:
Advtrace (k,n) = Pr?Exptrace (k,n) = 1? , GS,A GS,A
and say that GS is fully-traceable if for any polynomial-time adversary A, the two-argument function Advtrace (·, ·) is negligible, as per the definition of negligibility of two-argument functions given at
GS,A
1See section 5 for a detailed discussion of this case
the beginning of this section.
3 Relations to Existing Security Notions
We show that our formulations of anonymity and traceability are strong enough to capture all existing informal security requirements in the literature. This highlights the benefits of strong notions.
Unforgeability. A basic requirement of any digital signature scheme is that signatures cannot be forged, i.e., it is computationally unfeasible to produce message signature pairs (m, σ) that are accepted by the verification algorithm, without knowledge of the secret key(s). We did not include unforgeability among the main security properties of group signature schemes, since it immediately follows from full-traceability.
In order to define unforgeability, one can restrict the adversary used in the definition of full- traceability to just the second stage: in the first stage it does not ask for any secret key, and also, the secret key of the group manager is not part of its initial state St. Still, the adversary can obtain digital signatures of its choice using the signing oracle. In this case a successful attack against the full-traceability requirement reduces to producing a valid message signature pair (m, σ) such that message m was not queried to the signing oracle. The condition about the opening algorithm tracing the signature to a nonmember of the set of corrupted users is vacuously satisfied because this set is empty.
Exculpability. Exculpability (first introduced in [5]) is the property that no member of the group and not even the group manager can produce signatures on behalf of other users.
Clearly, a group signature scheme secure against full-traceability has also the exculpability property. If either the group manager or a user defeats the exculpability of a group signature scheme, then an adversary against full-traceability can be easily constructed. In the first case, the adversary simply follows the strategy of the group manager and produces a signature that is a forgery in the sense of full-traceability: it can not be traced to the one who produced it. In the second case, say user i can defeat the exculpability property. Then, an adversary as in the full-traceability experiment, which in the first stage makes a single request for gsk[i], and then follows the strategy of the user to produce the forgery, is successful against full-traceability.
Traceability. Originally [14], the name “traceability” was used to denote the functional property that if a message is signed with key gsk[i] and the opening algorithm is applied to the resulting signature, the output of the opening algorithm must be i. Later, the term has been overloaded to include an actual security requirement, namely that it is not possible to produce signatures which can not be traced to one of the group that has produced the signature. The two requirements seem to be first separated in [2] where the latter was identified with coalition resistance (see be- low). Nevertheless, a group signature scheme that is fully traceable, is also traceable (under either definition of traceability).
Coalition resistance. The possibility of a group of signers colluding together to generate signatures that cannot be traced to any of them was not part of the original formulation of secure group signature schemes. The requirement of traceability even in the face of attacks by a coalition of group members was explicitly considered for the first time only recently in [2], and termed coalition resistance. In the descriptions of the property, details such as whether the coalition is dynamically chosen or not are left unspecified. A strong formalization of coalition resistance can be obtained using the experiment for full-traceability in which the adversary is not given the secret key of the group manager. The rest remains essentially unchanged. It is then immediate that fully-traceable
group signature schemes are also coalition resistant.
Framing. Framing is a version of coalition resistance that was first considered in [15]. Here, a set of group members combine their keys to produce a valid signatures in such a way that the opening algorithm will attribute the signature to a different member of the group. As in the case of coalition resistance, framing has not been formally defined, issues similar to the one discussed above being left unspecified. A strong formalization for framing is the following: consider an experiment in which a user’s identity u is chosen at random from the set of all users, and all group secret keys, except the secret key of u, together with the secret key of the group manager are given to the adversary. The adversary wins if it manages to produce a signature which will open as user u, and we call a scheme secure against framing if no efficient adversary can win with non-negligible probability.
A group signature scheme that is fully-traceable, is also secure against framing. Indeed, an adversary B against framing can be turned into an adversary A against full-traceability as follows. It generates a random user identity and requests the secret keys of all other users. Then it runs adversary B with input these secret keys and the secret key of the group manager and outputs the forgery attempted by B. If B is successful in its framing attempt, then A defeats full-traceability.
Anonymity. As we have already discussed, anonymity is just a weaker form of full anonymity, in which the adversary does not have access to the opening oracle, and also, has no information of the member’s secret keys. Clearly, a scheme that is fully-anonymous is also anonymous.
Unlinkability. This is related to anonymity rather than full-traceability. The intuition is that a party after seeing a list of signatures, can not relate two signatures together as being produced by the same user. As for anonymity, it was implicit in previous definitions that the attacker was assumed not to be a group member. Again, realistic scenarios exist where this is not necessarily the case. It is thus necessary to consider distinct security notions for the two cases i.e. insider/outsider unlinkability. In either case, formalizing unlinkability is not an easy task because it is not clear how (possibly linked) signatures should be produced. For example we can require that it is compu- tationally hard to distinguish between a box that each time receives an input message produces a signature using a fixed secret key gsk[i], or a box where i is chosen uniformly at random for every invocation of the oracle. However, it is not clear why the uniform distribution should be used in the second case. Alternatively, we could let the adversary choose the distribution in the second case, but still in real applications it seems unjustifiable to assume that the signer is chosen each time independently at random and the choice of the signer at different times might be correlated. We considered various possible formalization of the notion of unlinkability, and in all cases we could prove that it follows from anonymity. Also, it seems that for any reasonable formulation of unlink- ability, one can prove that anonymity also follows. We conclude that anonymity and unlinkability are technically the same property, and only the easier to define anonymity property needs to be included in the security definition.
4 Our construction
We begin by describing the primitives we use, and then describe our construction.
4.1 Primitives
Digital signature schemes. A digital signature scheme DS = (Ks, Sig, Vf) is specified, as usual, by algorithms for key generation, signing and verifying. Our construction uses a digital signature
scheme that satisfies the standard notion of unforgeability under chosen message attack [21]. We now recall the definition.
Consider the following experiment Expunforg-cma(k), involving a forger A. A pair (pk,sk) of DS,A
public/secret keys for the signature scheme is generated by running the key generation algorithm on the security parameter (pk,sk) ←$ Ks(1k). Next, A is given as input pk, and is also provided
access to a signing oracle Sig(sk,·). The forger can submit (any number of) messages to the oracle, and obtain in return signatures, under secret key sk, on these messages. Finally, A outputs an attempted forgery (m,σ). The experiment returns 1 if σ is a valid signature on m, and m was never queried to the signing oracle, and returns 0 otherwise. We define the advantage of forger A as:
Advunforg-cma(k) = Pr h Expunforg-cma(k) = 1 i DS,A DS,A
where the probability is taken on the coins of the key generation algorithm, the coins of the signature
algorithm and the coins of the adversary. We say that a digital scheme DS is secure against forgeries
under chosen message attack if the function Advunforg-cma(·) is negligible for any polynomial-time DS,A
adversary A.
It is known that digital signature schemes, unforgeable under chosen message attack, exist
assuming one-way functions exist [27], and hence certainly assuming the existence of a family of trapdoor permutations.
Encryption schemes. A public-key encryption scheme AE = (Ke, Enc, Dec) is specified, as usual, by algorithms for key generation, encryption and decryption. Our group signature construction utilizes an encryption scheme that satisfies the standard notion of indistinguishability under chosen- ciphertext attack (IND-CCA) [26]. For completeness, we now recall the definition.
An IND-CCA adversary against AE is an algorithm A that operates in two stages, a choose
stage and a guess stage. For a a fixed bit b, the adversary works as follows. In the first stage the
algorithm is given a public key pke for encryption. It is also given access to a decryption oracle
which decrypts submitted ciphertexts using the secret key ske that corresponds to pke. At the
end of the first stage it outputs a pair of messages M0 and M1. The input of the algorithm to the
second stage is some state information, also produced at the end of the first stage, and a challenge
ciphertext C that is an encryption of Mb. At the end of the second stage (in which A still has
access to the decryption oracle but is not allowed to submit C as a query) the adversary outputs
a guess bit d that selects one or the other message. The adversary wins if he guesses successfully
which of the messages was encrypted. Let Expind-cca b(k) denote the random variable representing AE ,A
the outcome of A in the above experiment, when pke is obtained by running the key generation algorithm (with fresh coins) on security parameter k. The advantage function of A is defined as:
Advind-cca(k)=PrhExpind-cca 1(k)=1i−PrhExpind-cca 0(k)=1i AE,A AE,A AE,A
An encryption scheme AE is said to be IND-CCA secure if the function Advind-cca(·) is negligible AE ,A
for any polynomial-time adversary A.
It is known that the existence of trapdoor permutations implies that such encryption schemes
exists [17].
Simulation-sound Non-interactive zero knowledge proof systems. The last building block we need are simulation-sound NIZK proofs of membership in NP languages. The following presentation is along the lines of [18, 28].
An NP-relation over domain Dom ⊆ {0, 1}∗ is a subset ρ of {0, 1}∗ × {0, 1}∗ such that mem- bership of (x, w) ∈ ρ is decidable in time polynomial in the length of the first argument for all x in domain Dom. The language associated to ρ is the set of all x ∈ {0, 1}∗ such that there exists a
w for which (x, w) ∈ ρ. Often we will just use the term NP-relation, the domain being implicit. If (x,w)∈ρwewillsaythatxisatheoremandwisaproof ofx.
Fix a NP relation ρ over domain Dom. Consider a pair of polynomial time algorithms (P, V ), where P is randomized and V is deterministic. They have access to a common reference string, R. We say that (P, V ) form a non-interactive proof system for ρ [18, 9] over domain Dom if there exists a polynomial p such that the following two conditions are satisfied:
1. Completeness: ∀k ∈ N, ∀(x,w) ∈ ρ with |x| ≤ k and x ∈ Dom–
PrhR←$ {0,1}p(k);π←$ P(k,x,w,R) : V(k,x,π,R)=1i = 1.
2. Soundness: ∀k ∈ N, ∀Pb, ∀x ∈ Dom such that x ̸∈ Lρ–
PrhR←$ {0,1}p(k);π←Pb(k,x,R) : V(k,x,π,R)=1i ≤ 2−k .
We now detail the zero-knowledge requirement. Given a non-interactive proof-system (P, V ) for relation ρ, consider a simulator Sim, i.e. a polynomial-time algorithm running in two stages. In the randomized gen stage it produces a simulated common reference string R. We stress that it does so before seeing any theorem, based only on a bound on the theorem length. In the (w.l.o.g. deterministic) prove stage it takes as input a theorem x and state information passed on by the first stage, and then produces a simulated proof for the validity of x with respect to R.
This two phase behavior is not required explicitly in the definitions of [18, 9] but has been highlighted for example in [16]. The construction of [18] does have this property, and it is noted and used in other places too.
Zero-knowledge is defined by means of a distinguisher D which essentially tries to distinguish
between proofs produced by a prover (with respect to a real common random string), or a simulator
(with respect to a simulated common random string). More precisely, we consider two experiments
involving distinguisher D, Expzk 0 (k) and Expzk 1 (k). In the first experiment, a reference P,Sim,D P,Sim,D
string is produced via the simulator’s gen stage, while in the second it is a random string. In either case, the distinguisher chooses a theorem x based on R. It is mandated that x ∈ Dom. D is required to supply a correct witness for x relative to ρ, else it loses, meaning the experiment returns 0. (Note this further weakens the distinguisher and thus makes the computational zk requirement less stringent.) Having produced (x, w) ∈ ρ with x ∈ Dom, the simulator is given as challenge a proof π, produced according to the simulator’s prove stage in the first experiment, and according to the prover P in the second experiment. The zk-advantage of D is
Advzk (k)=PrhExpzk 1 (k)=1i−PrhExpzk 0 (k)=1i. P,Sim,D P,Sim,D P,Sim,D
We say that a non-interactive proof system (P, V ) is (computational) zero-knowledge if there exists
a polynomial time simulator Sim such that for any polynomial time distinguisher D the function
Advzk (·) is negligible. To show the dependency of Sim on (P, V ) we will say that (P, V, Sim) P,Sim,D
is a zero-knowledge proof system.
We point out that we only require single-theorem NIZK as opposed to multiple-theorem NIZK,
in that the distinguisher has a challenge real-or-simulated proof for only a single theorem. However, this weaker condition is made stronger by requiring that the simulator produce the reference string without seeing the theorem. Based on [18], there exists such zero-knowledge non-interactive proof system (P, V ) for any NP-relation ρ assuming the existence of trapdoor permutations.
The last property we require is simulation-soundness [28]. Let Π = (P,V,Sim) be a zero
knowledge interactive proof system for NP-relation ρ over domain Dom. Simulation-soundness
is defined using the experiment Expss (k) that we describe now. The experiment involves a Π,A
simulation-soundness adversary A working in two stages, choose and forge.
First, a “fake common” random string R, together with the associated trap-door information StS is generated by running the simulator: (R,StS) ←$ Sim(gen,k). The string is passed to the first stage of the simulation-soundness adversary, which outputs an element y ∈ Dom together with some information StA. The experiment uses the simulator to produce π, a proof of validity of y. Then (y,π,StA) are passed to the forge stage of A, at the end of which the adversary is required to output a pair (x,π′). The experiment returns 1 (i.e. the adversary wins) if the conditions (1) π′ ̸= π, (2) x ̸∈ and (3) Lρ, V (k, x, π′, R) = 1 are satisfied. Otherwise the experiment returns 0. The advantage of A is defined by
Advss (k) = Pr?Expss (k) = 1? Π,A Π,A
and we say that (P,V,Sim) is a simulation-sound if for all polynomial time adversaries A, there exists a negligible function ν (·), such that Advss (k) ≤ ν (k) for all k.
A Π,AA
From [18, 28], if trapdoor permutations exist, then any NP-relation has a simulation-sound,
non-interactive zero knowledge proof system.
4.2 Our construction
Overview. We now show that the building blocks above can be used to construct a group signature scheme GS = (GKg,GSig,GVf,Open) that is both fully-anonymous and fully-traceable. We fix a digital signature scheme DS = (Ks, Sig, Vf) and a public-key encryption scheme AE = (Ke, Enc, Dec) as above. We begin with an overview.
The group public key gpk consists of the security parameter k, a public encryption key pke, a verification key pks for digital signatures which we call the certificate verification key, and a reference string R. We denote by sks the signing key corresponding to pks, and call it the certificate creation key. The secret key gsk[i] of group member i contains a signature key ski with matching verification key pki and a certificate (i.e. signature) certi of ⟨i,pki⟩ under the certificate creation key. (For convenience the public key of the group gpk is also thrown into gsk[i].) The manager secret key gmsk is the decryption key ske corresponding to pke. The certificate creation key sks is however denied to the group manager. (This prevents the latter from issuing certificates for keys it generates itself, and is important to attain full-traceability). As far as our abstract key generation mechanisms goes, we imagine that this key, although created and used to produce certificates, is simply not given to the group manager. In “real life,” we would expect that a key-issuing entity, distinct from the group manager or players, maintains the certification keys. It can add members to the group dynamically via a protocol in which an aspiring group member i creates its own signature and verification keys ski,pki via Ks(k), and sends pki to the key issuer, who signs ⟨i,pki⟩ under pks to obtain certi and returns this to i along with k, R, pke, pks. The key issuer does not give the group manager the secret certificate creation key sks.
A group member i can produce a signature for a message m under pki by using its secret signing key ski. To make this verifiable without losing anonymity, it encrypts the verification key pki under pke and then proves in zero-knowledge that verification succeeds with respect to pki. However, to prevent someone from simply creating their own key pair ski,pki and doing this, it also encrypts i and its certificate certi, and proves in zero-knowledge that this certificate is a signature of ⟨i,pki⟩ under the certificate verification key pks present in the group public key. All proofs are with respect to reference string R of the group public key.
Group signature verification comes down to verification of the NIZK proofs. Opening is possible because the group manager has the decryption key ske.
Specification. We need to begin by specifying the witness relation ρ underlying the zero- knowledge proofs. We will then fix a proof system (P,V) for ρ and define the four algorithms
Algorithm GKg(1k, 1n)
R ←$ {0, 1}p(k) ; (pke, ske) ←$ Ke(1k) ; (pks, sks) ←$ Ks(1k) gpk ← (k, R, pke, pks) ; gmsk ← (k, pke, ske, pks) ;
For i ← 1 to n do
(pki, ski) ←$ Ks(1k) ; certi ← Sig(sks, ⟨i, pki⟩)
gsk[i] ← (i, pki, ski, certi, gpk) Endfor
Return (gpk, gmsk, gsk)
Algorithm GVf(gpk, (m, σ))
Parse gpk as (k, R, pke, pks) ; Parse σ as (C, π) Return V (k, (pke, pks, m, C), π, R)
Algorithm GSig(gsk[i], m)
Parse gsk[i] as (i, pki, ski, certi, gpk) Parse gpk as (k, R, pke, pks)
s←Sig(ski,m);r←$ {0,1}k;C←Enc(pke,⟨i,pki,certi,s⟩;r)
π←$ P(k,(pke,pks,m,C),(i,pki,certi,s,r),R);σ←(C,π); Returnσ
Algorithm Open(gmsk, gpk, m, σ)
Parse gmsk as (k, pke, ske, pks) ; Parse σ as (C, π) If V (k, (m, C), π, R) = 0 then return ⊥
Parse Dec(ske, C) as ⟨i, pk, cert, s⟩
Return i
Figure 2: Our construction: Group signature scheme GS = (GKg,GSig,GVf,Open) associated to digital signature scheme DS = (Ks, Sig, Vf), public-key encryption scheme AE = (Ke, Enc, Dec), and non-interactive proof system (P, V ).
constituting the group signature scheme in terms of P,V and the algorithms of DS and AE. Con- sider the relation ρ defined as follows: ((pke, pks, m, C), (i, pk′, cert, s, r)) ∈ ρ iff
Vf(pks, ⟨i, pk′⟩, cert) = 1 and Vf(pk′, m, s) = 1 and Enc(pke, ⟨i, pk′, cert, s⟩; r) = C .
Here M is a k-bit message, C a ciphertext and s a signature. We are writing Enc(pke,m;r) for the encryption of a message m under the key pke using the coins r, and assume that |r| = k. The domain Dom corresponding to ρ is the set of all (pke,pks,M,C) such that pke (resp. pks) is a public key having non-zero probability of being produced by Ke (resp. Ks) on input k, and M is a k-bit string. It is immediate that ρ is a NP relation over Dom, and consequently we can fix a non-interactive zero knowledge proof system (P, V ) for it. Based on this, the algorithms defining the group signature scheme are depicted in Figure 2.
4.3 Security Results
Fix digital signature scheme DS = (Ks, Sig, Vf), public-key encryption scheme AE = (Ke, Enc, Dec), NP-relation ρ over domain Dom, and its non-interactive proof system (P, V ) as above, and let GS =
(GKg, GSig, GVf, Open) denote the signature scheme associated to them as per our construction. We derive our main result (Theorem 4.3) via the following two lemmas.
Lemma 4.1 If AE is an IND-CCA secure encryption scheme and (P, V ) is a simulation sound, computational zero-knowledge proof system for ρ over Dom then group signature scheme GS is fully-anonymous.
Lemma 4.2 If digital signature scheme DS is secure against forgery under chosen-message attack and (P, V ) is a sound non-interactive proof system for ρ over Dom then group signature scheme GS is fully-traceable.
The scheme we have described is compact. Indeed, keys, as well as sizes of signatures of k-bit messages, are of size poly(k,log(n)). Since it is known that the existence of a family of trapdoor permutations implies the existence of the primitives we require [17, 6, 18, 28], we get:
Theorem 4.3 If there exists a family of trapdoor permutations, then there exists a compact group signature scheme that is fully-anonymous and fully-traceable.
We start with the proof of Lemma 4.1.
Proof: By the assumption that P is computational zero-knowledge for ρ over Dom, we can fix a simulator Sim such that (P,V,Sim) is a simulation sound zero knowledge non-interactive proof system for Lρ.
We show that for any given nice function n(·), and any polynomial time adversary B mounting an attack against full-anonymity of GS, one can construct polynomial time IND-CCA adversaries A0,A1 attacking AE, an adversary As against the simulation soundness of Π and a distinguisher D that distinguishes simulated proofs from real proofs, such that for all k ∈ N
Advanon (k, n(k)) ≤ Advind-cca(k) + Advind-cca(k) + Advss (k) + 2 · Advzk (k) (1) G S ,B AE ,A0 AE ,A1 Π,As P,Sim,D
By the assumption on the security of the building blocks of our group signature scheme, all functions
on the right side are negligible, therefore so is the function on the left. It follows from our definition
of negligibility of 2-argument functions, that Advanon (·,·) is negligible too, i.e. our construction GS,B
is a fully anonymous group signature scheme.
Adversaries against the encryption scheme. The details of adversaries A0,A1 against the encryption scheme AE is given in Figure 3. They are virtually identical, modulo parameter b by which their construction is parametrized, and so is the following description.
In the choose stage, Ab generates all individual secret keys as well as the certification/verification keys. The difference from a real group signature scheme is that the group manager public key (used for encryption) is obtained from the environment in which A is run (the CCA experiment) and that the random string R in the public key of the encryption scheme is obtained by using the simulator Sim.
Then, Ab runs B against the group signature scheme created this way. In doing so, it needs to answer all opening queries that B may make. This is possible, using the decryption oracle: when a query to the opening oracle is made by B, adversary Ab intercepts this query and checks to see if the signature is valid (this is easy, since Ab possesses gpk.) Then, Ab submits the encrypted part of the signature to the decryption oracle, and from the plaintext, A extracts the identity of the alleged signer which it passes to B.
Algorithm ADec(ske,·)(choose, pk ) Algorithm D(choose, k, R) bek
(pks, sks) ←$ Ks(1k)
(stS , R) ←$ Sim(gen, k) gpk ← (k, R, pke, pks) For i ← 1 to n(k) do
(pke, ske) ← Ke(1 ) (pks, sks) ← Ks(1k) gpk ← (k, R, pke, pks) Fori←1ton(k)do
(pki, ski) ← Ks(1k)
certi ← Sig(ski, ⟨i, pki⟩)
gsk[i] ← (i, pki, ski, certi, gpk)
EndFor
(st, m, i0, i1) ←$ B(·)(choose, gpk, gsk)
(pki, ski) ←$ Ks(1k) $
certi ← Sig(sks, ⟨i, pki⟩)
gsk[i] ← (i, pki, ski, certi, gpk) EndFor
(st, m, i0, i1) ←$ B(·)(choose, gpk, gsk)
sb ←$ Sig(skib,m)
St ← (m,st,stS,pke,pks) Mb ←⟨ib,pkib,certib,sb⟩ M ̄b ← 0 | M b |
Return (M0, M1, St)
Adversary ADec(ske,·)(guess, St, C) b
Parse St as (m,st,stS,pke,pks)
π ← Sim(prove,stS,(pke,pks,m,C))
Run B(·)(guess, st, (C, π))
If at any point B makes a valid query (C,π′)
Then d←b
Else d is the output of B Return d
b ←$ {0,1}; r ←$
s ← Sig(skib , m)
C ← Enc(pke, ⟨ib, pkib , certib , s⟩; r) St←(st,b,C)
Return (St, (pke, pks, m, C), (ib, pkib , certib , s, r))
Algorithm D(guess, St, π) Parse St as (st,b,C)
d ← B(·)(guess,st,(C,π)) If d = b Then Return 1
Else Return 0
{0,1}k
Figure 3: Adversary Ab (b = 0,1) is against the security of the encryption scheme ; D is a distinguishser against the zero knowledge property of the interactive proof system
When B outputs a message m and two identities i0, i1, Ab creates two challange plaintexts M0, M1, (to be returned to the IND-CCA experiement at the end of the choose stage of Ab). The plaintexts are computed as follows: Mb is the plaintext of the encrypted part of a group signature on m produced by ib and M ̄b is an all-zero string of length equal to that of Mb.
We now move to the guess stage of Ab in which the adversary receives as input a ciphertext C, which is the encryption of one of the two messages, M0 and M1. Next, Ab runs the simulator to obtain a proof π of validity for (pke,pks,m,C). This is always possible, event in the case when C encrypts M ̄b. The challange signature that is passed to the second stage of B is (C,π) which Ab now simulates. The final output of Ab is computed as follows: if during this stage B makes a valid query (C,π′) to the opening oracle (i.e. it manages to produce a different proof of validity for C), then the guess bit d is set to b, otherwise it is set to whatever B outputs.
Notice that further opening queries of B can be answered by Ab using the decryption oracle (as described above). However, we have to make sure that the challenge ciphertext C is never queried to the decryption oracle. This is true, since whenever a valid query (C,π′) is issued by B to the opening oracle, adversary Ab, instead of submitting C to the decryption oracle, simply outputs b and terminates.
The distinguisher for zero-knowledge. The distinguisher D (given in Figure 3), also starts out by creating an instance of the group signature scheme GS. The keys for the encryption schemes, the individual signing keys and the keys for certyfing/veryfing individual public keys are obtained by running the resepctive key generation algorithms. The string R that is part of the public key is supplied to D by the environment in which it is run.
Then, by running B against the group signature scheme, it obtains a message m and two identities i0, i1 for which B claims it can distinguish group signatures on m. Notice that D can easily answer any query that B may make to the opening oracle, since it possesses gmsk. The challange group signature that D passes to the second stage of B is created as follows. One of the two signers i0 and i1 is chosen, by flipping uniformly at random a bit b, and the plaintext corresponding to a signature on m created by ib is encrypted under the public key of the group manager. It then outputs (pks, pke, m, C) ∈ Lρ together with the corresponding witness. The input to the second stage of D contains π, which is a proof of membership of (pks, pke, m, C) to Lρ (which depending on the environment is either simulated or real). In this stage, D creates a group signature (C,π) on m and feeds it to the second stage of B. The final output of D is whatever B outputs.
Algorithm ASim(prove,stS ,·)(choose, R) s
(pke, ske) ←$ Ke(1k)
(pks, sks) ←$ Ks(1k) gpk ← (R, pke, pks) For i ← 1 to n(k) do
(pki, ski) ←$ Ks(1k)
certi ←$ Sig(sks,⟨i,pki⟩)
gsk[i] ← (i, pki, ski, certi, gpk) EndFor
(st, m, i0, i1) ←$ B(·)(choose, gpk, gsk)
sb ←$ Sig(skib,m)
St ← (m,st,stS,pke,pks) M1 ←⟨i1,pki1,certi1,s1⟩ M0 ← 0|M1|
C ←$ Enc(pke,M0)
π ← Sim(prove,stS,(pke,pks,m,C)) [oracle query] Run B(·)(guess, st, (C, π))
If B makes a valid query (C,π′) Output ((pke, pks, m, C), π′)
Figure 4: Adversary As is against simulation-soundness
The simulation-soundness adversary. The adversary As against the simulation soundness is given in Figure 4. It creates an instance for the group signature scheme GS, by generating all keys. The only difference from a “real” group signature scheme is that the random string R that is part of the public key is obtained from the environment in which As runs (i.e. it is generated by the simulator). Then As runs B against the group signature scheme until B outputs the message and the two identities i0 and i1 for which it can distinguish signatures. The challenge signature (C, π) that As passes to the second stage of B is such that C is the encryption of the all-zero string (of
appropriate length) and π is a simulated proof of validity. Finally, A tracks the queries that B makes to the opening oracle: if B makes a valid query (C, π′) then As outputs ((pke, pks, m, C), π′), otherwise it fails.
Putting it all together. We now explain how to relate the advantages of the four adversaries described above with the advantage of B (the adversary against full-anonymity that they all run as a subroutine.) We start with the distinguisher.
Recall that under experiment Expzk 1 (k), the string R passed to the distinguisher is an actual P,Sim,D
random string; so D runs B against a group signature scheme, generated according to the key
generation algorithm GKg. If (m, i0, i1) is the output of the choose stage of B, the signature passed
to the guess stage of B is the real signature of ib, where b is chosen at random. So, D outputs 1,
exactly when B guesses correctly which user produced the signature, i.e. it wins in Expanon-b(k), GS,B
no matter what D’s choice of b is. We can formalize the above as follows: PrhExpzk 1 (k)=1i
P,Sim,D
= Pr[B(guess)=1 | b=1]·Pr[b=1]+Pr[B(guess)=0 | b=0]·Pr[b=0]
= 1Pr?Expanon-ia 1(k,n(k))=1?+1Pr?Expanon-ia 0(k)=0? 2 GS,B 2 GS,B
= 1Pr?Expanon-ia 1(k,n(k))=1?+1?1−Pr?Expanon-ia 0(k,n(k))=1?? 2 GS,B 2 GS,B
= 1 + 1 Advanon (k, n(k)) 2 2 GS,B
Eliminating the fractions, we have that: 2·PrhExpzk 1
(k), and relate it to the advantages of adversaries A0,A1 and As. The key observation is that in all these adversaries, B is run as a subroutine against a group signature scheme in which keys are generated according the same distribution: the only difference from a real group signature scheme is that the random string that is part of the group public key, is obtained from the simulator. The second important observation is related to the input to the guess stage of B. Let (st, m, i0, i1) be the output of the first stage of B. The challenge signature (C, π) passed to the second stage of B is sampled from one of distributions D0, D1 and D0k that we now describe. For b = 0, 1, the elements of distribution Db are signature- looking pairs, (C, π), where C is the encryption (under the public key of the group manager) of a plaintext that ib would normally encrypt when creating a group signature on m, and π is a proof of validity obtained by running the simulator on (pke, pks, m, C). The distribution D0k is obtained similarly, but C is the encryption of the all-zero message. We will write B(0),B(1) and B(0k) for the outcome of the second stage of B when the challenge signature comes from distribution D0, D1 and D0k , respectively. Finally, we consider the following events concerning the behavior of B. We willdenotebyASK0,ASK1andASK0k theeventthatwhenthechallengesignature(C,π)issampled from distribution D0,D1 and D0k respectively, then during the second guess stage B makes a valid query (C, π′) to the opening oracle. By NASK0, NASK1 and NASK0k we denote the corresponding
opposite events.
We can now analyze, using the above notation, the success of the above adversaries when run under the various experiments for which they are intended.
P,Sim,D
We now analyze the success of D under experiment Expzk 0
(k)=1i=1+Advanon (k,n(k)) (2) GS,B
P,Sim,D
1. From the description of A1, it can be seen that in the experiment Expind-cca 1(k), adversary AE ,A1
A1 always passes to the second stage of B a challenge signature sampled from D1. From the definition of A1, it is immediate that there are two cases in which A1 outputs 1 in this experiment: if event ASK(1) happens, or if B outputs 1 and NASK(1) happens. Formally:
PrhExpind-cca 1(k)=1i=Pr[B(1)=1∧NASK )]+Pr[ASK ] (3) AE,A1 1 1
The relation that we actually need (and immediately follows the above) is that: PrhExpind-cca 1(k) = 1i ≥ Pr[B(1) = 1] (4)
AE ,1
2. When A1 is run in experiment Expind-cca 0(k), the challenge signature passed to B is sampled
AE ,A1
from the distribution D0k . A similar reasoning as above leads to the relation:
h ind-cca0 i h k i Pr ExpAE,A1 (k)=1 =Pr B(0 )=1∧NASK0k
+Pr[ASK0k ] (5) 3. Now we focus on the experiment Expind-cca 1(k). The challenge signature passed to B comes
AE ,A0
from distribution D0k , so the experiment returns 1, exactly when B(0k) = 1 and event NASK0k
occurs (otherwise the experiment returns 0):
h ind-cca1 i h k i
Pr ExpAE,A0 (k)=1 =Pr B(0 )=1∧NASK0k
4. When A0 is run under experiment Expind-cca 0(k), the challenge signature is sampled from
AE ,A0
D0, so the experiment returns 1 only when both B(0) = 1 and event NASK0 happen (otherwise
the experiment returns 0):
PrhExpind-cca 0(k)=1i=Pr[B(0)=1∧NASK ]≤Pr[B(0)=1] (7)
AE,A0 0
5. Notice that the simulation-soundness adversary As passes to the second stage of B a sample from distribution B(0k). Since, (pke, pks, m, C) ̸∈ Lρ (here C is the encryption of the all-zero message), As wins in the simulation soundness experiment exactly when B makes a valid query (C, π′) to the decryption oracle in which π′ ̸= π; so:
Advss (k) = Pr [ ASK k ] (8) Π,As 0
Combining this last relation with equations (5) and (6) we obtain that
PrhExpind-cca 0(k)=1i−PrhExpind-cca 1(k)=1i=Advss (k) (9)
AE ,A1 AE ,A0 Π,As
6. The success probability of D under experiment Expzk 0 (k) is determined as follows. From
P,Sim,D
the description of D, the signature passed to the second stage of B is sampled from D0, or
D1, the choice of distribution being determined by the random bit b. So, D outputs 1 exactly when B correctly guesses which is the distribution from which the challenge signature was chosen. Formally:
PrhExpzk 0 (k)=1i P,Sim,D
= Pr[B(0)=0]·Pr[b=0]+Pr[B(1)=1]·Pr[b=1] = 12(1−Pr[B(0)=1]+Pr[B(1)=1])
(6)
(10)
Using equations (4) and (7) it immediately follows that:
2·PrhExpzk 0 (k)=1i≤1+PrhExpind-cca 1(k)=1i−PrhExpind-cca 0(k)=1i. (11)
P,Sim,D AE ,A1 AE ,A0
Now, in the right hand side of the above inequality, we add and substract the right and the left
sides of Equation (9) and obtain: 2·PrhExpzk 0 (k)=1i
P,Sim,D ≤1
+ PrhExpind-cca 1(k)=1i−PrhExpind-cca 0(k)=1i AE ,A1 AE ,A1
+ PrhExpind-cca 1(k)=1i−PrhExpind-cca 0(k)=1i AE ,A0 AE ,A0
+ Advss (k) Π,As
= Advind-cca(k) + Advind-cca(k) + Advss (k) AE ,A1 AE ,A0 Π,As
We can now calculate the advantage of distinguisher D, by combining the above equation with Equation 2:
2·Advzk (k) = 2·?PrhExpzk 1 (k)=1i−PrhExpzk 0 (k)=1i? P,Sim,D P,Sim,D P,Sim,D
≥ Advanon (k, n(k)) − Advind-cca(k) − Advind-cca(k) − Advss (k)
GS,B AE,A0 and by rearranging the terms we obtain
Advanon (k, n(k)) ≤ Advind-cca(k) + Advind-cca(k) + Advss
G S ,B AE ,A0 AE ,A1 Π,As
as desired.
We now prove Lemma 4.2.
AE,A1 Π,As
Proof: We obtain our result as follows. We show how to construct adversaries A1 and A2 against digital signature scheme DS, and by using the assumption that (P, V ) is a sound proof system for ρ, we show that for any adversary B against full-traceability of GS, and any nice function n : N → N,
Advtrace (k, n(k)) ≤ 2−k + Advunforg-cma(k) + n(k) · Advunforg-cma(k) GS,B DS,A1 DS,A2
Since we assume that the digital signature scheme DS is secure, it follows that the right hand side of the inequality is a negligible function (of the security parameter) so, the advantage function on the left is also negligible. Thus, according to the definition, GS is a fully-traceable group signature scheme.
So, let B be a full-traceability adversary against our group signature scheme and let C be the set of group members that B corrupts during its attack. We first give a classification of the types of forgeries that B can produce.
Case 0. The simplest case is when the forgery (m, (C, π)) is such that (pke, pks, m, C) ̸∈ Lρ, yet the signature appears to be valid, i.e. π is a proof for a false statement. We call these forgeries of type 0.
Otherwise, the plaintext underlying C is of the form ⟨i, pk, cert, s⟩ for some i, pk, cert, s, user i is not part of the corrupted set, i.e. i ̸∈ C and relations
(k) + 2 · Advzk P,Sim,D
(k)
1. Vf(pks, ⟨i, pk⟩, cert) = 1 and 2. Vf(pk,m,s)=1
hold. Depending on the membership certificate, we distinguish the following two cases:
Case 1. The pair i, pk was not certified by the group manager (this is the case, for instance, when i is not a valid user identity.) In this case, the coalition manages to forge a group membership certificate cert for identity i. We call these forgeries of type 1.
Case 2. The last case is when i, pk was certified by the group manager, in which case i is a valid user identity. If this is true, then it must be the case that i ̸∈ C, and the (i, m) is not submitted to the signing oracle. Which in particular implies that the coalition produces a valid signature s on m. We call these forgeries of type 2.
We can immediately bound the probability that B produces a forgery of type 0. Indeed, since (P, V ) is a sound proof system for ρ, for any security parameter k, and any polynomial time forger B,
Pr[Boutputs(C,π):(pke,pks,m,C)̸∈Lρ andV((m,C),π)=1]≤2−k (12) The details of adversaries A0,A1 are given in Figure 5. Adversary A1 is intended to run in the
experiment Expunforg-cma(k), and as such, it has access to a signing oracle Sig(sks, ·). The adversary DS,A1
creates an instance of the group signature scheme, and uses the signing oracle to certify individual public keys. More precisely, it starts by generating the public/secret pair used for encryption, (pke,ske) by itself, and then produces individual certificates using the signing oracle, i.e. for each user j, it generates a pair of individual signing/verifying keys (skj,pkj) and submits ⟨j,pkj⟩ to the oracle. The answers returned by the oracle are individual certificates certj = Sig(sks, ⟨j, pkj ⟩). Finally, it runs adversary B against GS. In order to perfectly emulate the environment in which B is run, adversary A1 needs to answer the queries that B makes, i.e. it needs to produce group signatures on messages of B’s choice, and also it needs to return to B the secret group signing key of users that it corrupts. This can be easily done, since A1 possesses the secret keys of all the users.
When B stops and produces an attempted forgery (m,(C,π)), A1 decrypts C and obtains the
certificate cert, and the pair identity/individual public key, i, pk, used to create the group signature.
If the forgery that is output is of type 1 (the group manager never certifies ⟨i, pk⟩), then the message
⟨i, pk⟩ was never queried to the signing oracle and Vf(pks, ⟨i, pk⟩, cert) = 1. The pair (⟨i, pk⟩, cert)
is therefore a successful forgery in the Expunforg-cma(k) experiment. Therefore, for a fixed security DS,A1
parameter k, if E1 is the event that B outputs a forgery of type 1 in the experiment describing an attack on full-traceability of GS, then
Advunforg-cma(k) = Pr [ E1 ] (13) DS,A1
We now show how to construct an adversary that exploits the second type of forgeries. Adversary A2 is intended to run in the experiment Expunforg-cma(k), defining the security of digital signature
DS,A2
DS. As such, it has access to a signing oracle Sig(sk,·), and is given as input the corresponding
verification key pk. It starts out by construction an instance of the group signature scheme GS as follows. It generates the certification key sks together with the corresponding key pks and also the opening key ske together with the corresponding key pke. Then, it generates all but one individual signing-verifying keys {skj,pkj}{j̸=i}. The individual signing key for user i will be the signing key sk of the oracle to which A2 has access. Furthermore, A2 creates individual membership certificates simply by signing ⟨j,pkj⟩ for users j ̸= i, and ⟨i,pk⟩ for user i.
Sig(sk,·) Algorithm A1
Adversary ASig(sk,·)(pk) 2
R←$ {0,1}p(k)
(pke, ske) ← Ke(k) ; (pks, sks) ← Ks(k) i ←$ {1, 2, ..., n(k)}
(pk) $k
R←$ {0,1}p(k) $$
(pke, ske) ← Ke(1 )
gpk ← (k, R, pke, pks) gmsk ← (k, n, pke, ske, pks) For j ← 1 to n(k) do
(skj,pkj)←$ Ks(k)
certj ←$ Sig(sk,⟨j,pkj⟩)
gsk[j] ← (j, pkj , skj , certj , gpk) EndFor
Run B
Until B stops and outputs (m, (C, π)) Parse Dec(ske, C) as ⟨i, pk′, cert′, s⟩ Return (⟨i, pk′⟩, cert′)
For j ← 1 to n(k) (except i) do (skj , pkj ) ←$ Ks(k)
$
certj ←Sig(sks,⟨j,pkj⟩)
gsk[j] ← (j,pkj,skj,certj,gpk) Endfor
cert ←$ Sig(sks, ⟨i, pk⟩) gpk ← (R, pke, pks) gmsk ← (pke, ske, pks) Run B
- if in the choose stage B requests gsk[i] the algorithm fails;
- when B makes an oracle query (j, m) do
σ ←$ GSig(gsk[j], m); return σ to B;
- when B makes an oracle query (i, m) do
s ←$ Sig(sk,m);
C ←$ Enc(pke, ⟨i, pk, cert, s⟩; r);
π ←$ P (k, (pke, pks, m, C), (i, pk, cert, s, r)); return (C, π) to B
Until B stops and returns (m, (C, π)) Parse Dec(ske, C) as ⟨(i, pk′, cert′, s)⟩ Return (m, s)
Figure 5: Construction of two cma-forger A1 and A2 against DS from an adversary B against full-traceability of GS. Note that n(·) is a fixed nice function.
Next A2 runs B against GS created this way and thus needs to be able to answer all oracle queries that B may make. Requests for signatures on messages can be easily answered. Requests of the type (j,M), with j ̸= i, are answered by using secret group signing key of j (which it A2 created by itself). Requests of the type (M, i) are handled by first submitting M to the signing oracle, thus obtaining s = Sig(sk,M), and then by creating the rest of the group signature by itself. Finally, A2 can also answer all requests for the group signing secret keys of group members (notice that gsk[i] is not requested, since otherwise opening the signature would lead to a member of the set of corrupted members and the forgery would not be successful).
Furthermore, the message (i, m) was not queried to the group signing oracle (otherwise it is not
a valid forgery), which in particular means m was not queried to the signing oracle Sig(sk,·) to
which A2 has access. Altogether, this amounts to the fact that (m, s) is a successful forgery of A2
in the Expunforg-cma(k) experiment. We can now relate the probability that B outputs a forgery of DS,A2
type 2 in the full-traceability experiment with the success probability of A2 in the Expunforg-cma(k) DS,A2
experiment, by observing that A2 wins precisely when B outputs a successful forgery and A2 22
correctly guesses the identity i that underlies the forged signature. Since the latter event happens with probability 1/n(k) and is independent of the former we obtain:
Advunforg-cma(k) = 1 (k) · Pr [ E2 ] (14) DS,A2 n
Using Equations (12),(13) and (14) we can bound the advantage of B as desired:
Advtrace (k, n(k)) GS,B
= Pr ? B wins in the experiment Exptrace (k) ? GS,B
= Pr [ B outputs a successful forgery (m, (C, π)) ]
= Pr[((pke,pks,m,C)̸∈Lρ andV((m,C),π)=1) orE1 orE2]
≤ 2−k + Advunforg-cma(k) + n(k) · Advunforg-cma(k) DS,A1 DS,A2
5 Dynamic Groups and Other Extensions
In the previous sections we considered static group signatures schemes. i.e., schemes where the size and membership of the group do not change over time. In this section we discuss various extensions of the basic definition, including schemes where the group is dynamic. i.e., members can join and leave the group over time. Following standard terminology [24] we refer to these groups as partially or fully dynamic.
Partially dynamic groups. These are groups supporting either join (incremental) or leave (decremental) operation. Here we concentrate on incremental groups, and postpone the discussion of leave operation to the next paragraph. In an incremental group signature scheme, the key generation algorithm produces (beside the group public key gpk) two secret keys: an issuing key gisk and an opening key gmsk. No signing keys gsk are output by the key generation algorithm. The two keys gisk,gmsk are given to two different group managers, one of which has authority on the group membership, and the other has authority on traceability. Using gisk, the key issuer can generate (possibly via an interactive process) signing keys gsk[i] and distribute them to perspective group members (which we identify with the index i). The basic definition of security is essentially the same as described in the previous sections. Key gisk is given to the adversary in the definition of anonymity, but not in the definition of traceability, as knowledge of this key would allow to generate “dummy” group members and use their keys to sign untraceable messages. Alternatively, one can postulate that if the signature opener cannot trace a signature, then he will blame the key issuer. Our construction (and proof of security) from section 4 can be easily extended to support incremental group operations, with the certificate creation key sks used as gisk.
Although the above definition allows the group to change over time, the security properties are still static: a signer i that join the group at time t, can use the newly acquired key gsk[i] to sign documents that predate time t. This problem can be easily solved enhancing the signatures with an explicit time counter, and using the technique of forward security. Before explaining the connection with incremental groups, we discuss forward security, which may be a desirable security feature on its own. As for standard digital signature schemes [7], forward security for group signatures is defined using a key evolution paradigm. The lifetime of the public key is divided into time periods, and signing keys of the group members change over time, with the key of user i at time j denoted
gskj[i]. At the end of each time period, each user updates his key using an update algorithm gskj+1[i] = GUpd(gskj[i]). Although the forward security requirement for group signature schemes was already considered before [29], that definition has a serious security flaw: [29] only requires that no adversary, given gskt[i], can efficiently recover gskj[i] for any j < t. This is not enough.2 We define forward secure group signature schemes requiring that an attacker should not be able to produce valid signatures for any earlier time period.
Our scheme from Section 4 can be modified to achieve forward security, by replacing the sig- nature scheme used by group members with a forward secure one DS = (Ks,Vf,Sig,Upd).time period j, user i has the group signing key gskj[i] = (k,R,i,pki,ski,j,certi,pke,pks), where ski,0 is obtained by running the key generation algorithm of DS and ski,j is the result of evolving ski,0 j times. The key update algorithm GUpd for the group signature scheme is GUpd(gskj[i]) = (k, R, i, pki, Upd(ski,j ), certi, pke, pks), and group membership certificates are preserved across dif- ferent time periods, since the individual public keys remain unchanged. If the individual signature scheme is forward secure, and the signature scheme used to certify individual scheme is secure against chosen message attack, then we postulate that the group signature scheme described above is a secure group signature scheme.
In the context of dynamic group signature schemes, signing keys are not stolen by an adversary, but given by the key issuer to the group members. Still, if the signature scheme is forward secure, then the group member cannot use the (legitimately obtained) key to sign documents the predate the joining time. A (forward) secure partially dynamic group signature scheme supporting the join operation is obtained letting the key issuer generate key gskt[i] when user i joins the group at time t.
Fully dynamic groups. Now consider a group where members can both join and leave the group. The issue of members leaving the group is much more delicate than the one of members joining the group, and several alternative (and incompatible) definitions are possible. As for partially dynamic groups, the signing keys gskj[i] may vary over time, but this time also the public key gpkj is allowed to change. Consider a signature σ produced (using key gska[i]) at time a by some user i who belonged to the group at time 1, but not at times 0 and 2, Now, say σ is verified at time b (using key gpkb). When should σ be accepted by the signature verification algorithm? There are two possible answers: (1) if i was a group member when then signature was generated, or (2) if i belonged to the group at the time verification algorithm is invoked.3 Clearly, there is no “right” answer, and what definition should be used depends on the application. In either case, different kinds of inefficiency are necessarily introduced in the protocol. In case (2), σ should be accepted if b = 1, but not if b = 0 or b = 2. In particular, the public keys gpkj must be different. This is undesirable because it requires the verifier to continuously communicate with the group manager to update the group public key.4 Moreover, this definition raises potential anonymity problems: verifying the same signature against different public keys gpkj, one can determine when the signer joined and left the group, and possibly use this information to discover the signer identity. Now consider case (1), where signatures are valid only if signer belongs to the group at the time the
2Consider a scheme where gskj [i] = (kj ; hj ) GUpd(kj ; hj ) = kj ; g(hj ) for some one way permutation g, and only the first part of the key kj is used by the signing algorithm. Such a scheme would certainly satisfy the definition of [29], but it is clearly not forward secure: even if the past keys cannot be recovered, the adversary can still forge messages in the past!
3Notice that in the first case, signatures should remain valid (and the signer anonymous) even after the signer leaves the group, while in the second case removing the signer from the group should immediately invalidate all of its signatures.
4Alternatively, one can consider public keys of the form gpkj = (gpk,j), where the time dependent part can be supplied autonomously by the verifier. But it is easy to see that in this case the life time of secret key gsk[i] needs to be decided in advance when the user i joins the group.
signature is issued. This time, the public key may stay the same throughout the lifetime of the group, but the key update function gskj[i] = GUpd(gskj−1[i]) should not be publicly computable by the group members. This introduces inefficiency, as the group members now need to interact with the key issuer to update their signing key from one time period to the next.
Our construction can be easily adapted to satisfy either definition of security for fully dynamic groups, e.g., by rekeying the entire group at the end of each time period. Due to the high (but unavoidable) cost of rekeying operations, fully dynamic group signatures should be used only if required by the application, and in all other situations the simpler incremental groups are clearly preferable.
Dishonest group managers. The last extension to the definition we discuss pertains the case where the group manager holding gmsk is not honest. The experiments we gave in Section 2, only capture the situation where the adversary obtained the group manager’s secret key. If the group manager is truly dishonest, one should also assume that he does not behave as prescribed when applying the opening algorithm. For example, when asked to open a signature he can falsely accuse an arbitrary user (i.e. he does not use his secret key), or claim that the signature can not be open (e.g. he changes the secret key).
We consider a solution in which when opening a signature the group manager (on input opening key gmsk, message m and signature σ) outputs not only a user identity i, but also a “proof” τ. This proof can be (publicly) verified by a “judging” algorithm GJudge (which is added to the syntax of a group signature scheme,) such that if Open(gmsk,m,σ) = (i,τ) then GJudge(m,σ,i,τ) = true. Within this framework, it is possible to formally capture security requirements regarding dishonest behavior of the group manager, as described at the beginning of this section.
Our scheme from Section 4 can be easily modified accordingly. We use an authenticated en- cryption scheme AE in which when decrypting a ciphertext, one also recovers the randomness that was used to create it. Opening a signature (C,π) is done as follows: the group manager recovers the plaintext underlying C as ⟨i, pki, certi, s⟩ and also recovers the randomness r that was used to create C. Then, it outputs (i,τ), where τ = (⟨i,pki,certi,s⟩,r), is the “proof” that the signature was created by user i. The judging algorithm GJudge simply checks whether C is the result of encrypting ⟨i, ski, pki, certi, s⟩ with pke using randomness r.
References
[1] R. Anderson. Invited talk. Fourth Annual Conference on Computer and Communications Security,1997.
[2] G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition- resistant group signature scheme. In M. Bellare, editor, CRYPTO’00, volume 1880 of LNCS, pages 255–270. Springer-Verlag, 2000.
[3] G. Ateniese and G. Tsudik. Quasi-efficient revocation in group signature schemes. Available at
[4] G. Ateniese and G. Tsudik. Group signatures `a la carte. In ACM Symposium on Discrete Algorithms, pages 848–849. ACM Press, 1999.
[5] G. Ateniese and G. Tsudik. Some open issues and directions in group signature. In Financial Crypto’99, volume 1648 of LNCS, pages 196–211. Springer-Verlag, 1999.
[6] M. Bellare and S. Micali. How to sign given any trapdoor permutation. Journal of ACM, 39(1):214–233, January 1992.
[7] M. Bellare and S. Miner. A forward-secure digital signature scheme. In M. Wiedner, editor, CRYPTO’99, volume 1666 of LNCS, pages 431–448. Springer-Verlag, 1999.
[8] M. Bellare, H. Shi, and C. Zhang. Foundations of group signatures: the case of dynamic groups.
[9] M. Blum, A. DeSantis, S. Micali, and G. Persiano. Non-interactive zero-knowledge proof
systems. SIAM Journal on Computing, 20(6):1084–1118, December 1991.
[10] E. Bresson and J. Stern. Efficient revocation in group signatures. In PKC’2001, volume 1992
of LNCS, pages 190–206. Springer-Verlag, 2001.
[11] J. Camenisch. Efficient and generalized group signature. In EUROCRYPT’97, volume 1233
of LNCS, pages 465–479. Springer-Verlag, 1997.
[12] J. Camenisch and M. Michels. A group signature scheme with improved efficiency. In K. Ohta and D. Pei, editors, ASIACRYPT’98, volume 1514 of LNCS, pages 160–174. Springer-Verlag, 1999.
[13] J. Camenisch and M. Stadler. Efficient group signatures schemes for large groups. In B.Kaliski, editor, CRYPTO’97, volume 1294 of LNCS, pages 410–424. Springer-Verlag, 1997.
[14] D. Chaum and E. van Heyst. Group signatures. In D. W. Davis, editor, EUROCRYPT’91, volume 547 of LNCS, pages 257–265. Springer-Verlag, 1991.
[15] L. Chen and T. P. Pedersen. New group signature schemes. In A. DeSantis, editor, EURO- CRYPT’94, volume 950 of LNCS, pages 171–181. Springer-Verlag, 1994.
[16] A. DeSantis and M. Yung. Cryptographic applications of the non-interactive metaproof and many-prover systems. In A. Menezes and S. Vanstone, editors, CRYPTO’90, number 537 in LNCS, pages 366–377. Springer-Verlag, 1990.
[17] D. Dolev, C. Dwork, and M. Naor. Nonmalleable cryptography. SIAM Journal of Computing, 30(2):391–437, 2000.
[18] U. Feige, D. Lapidot, and A. Shamir. Multiple non-interactive zero-knowledge proofs under general assumptions. SIAM Journal on Computing, 29(1):1–28, September 1999.
[19] O. Goldreich. A uniform-complexity treatment of encryption and zero-knowledge. Journal of Cryptology, 6(1):21–53, 1993.
[20] S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Science, 28:270–299, 1984.
[21] S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal of Computing, 17(2):281–308, April 1988.
[22] S. Micali, C. Rackoff, and B. Sloan. The notion of security for probabilistic cryptosystems. SIAM Journal of Computing, 17(2):412–426, 1988.
[23] M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In STOC’90, pages 427–437, 1990.
[24] N. I. of Standards and Technology. Dictionary of algorithms and data structures.
[25] H. Petersen. How to convert any digital signature scheme into a group signature scheme. In Proceedings of Security Protocols Workshop’97, pages 177–190, 1997.
[26] C. Rackoff and D. Simon. Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack. In CRYPTO’91, pages 433–444, 1992.
[27] J. Rompel. One-way functions are necessary and sufficient for secure signatures. In 22nd Annual Symposium on Theory of Computing, pages 387–394. ACM, ACM Press, 1990.
[28] A. Sahai. Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext secu- rity. In FOCS’99, pages 543–553, 1999.
[29] D. Song. Practical forward-secure group signature schemes. In ACM Symposium on Computer and Communication Security, pages 225–234, November 2001.
