1. Introduction

In traditional digital signature schemes, the identity of signer can be identified with the corresponding the public key. It is hard to protect identity privacy.

In 1991, Chaum et al. introduced the concept of a group signature scheme [1]. A group signature scheme allows any member of a group to sign messages on behalf of a group while his identity is kept secret from the verifier. So a group signature scheme has the anonymity. Meanwhile, to prevent abuses, the group is controlled by a group manager that has the ability to open a group signature, i.e. to reveal the identity of the signature's originator (traceability). Furthermore, in 2005, Bellare, Shi and Zhang [2-3] extended these notions to dynamic groups and added the notion of non-frameability. In dynamic group scheme, it allows a new user to join group. The non-frameability can guarantee that any one (including the group manager) should not be able to produce a valid group signature on behalf of another member. Obviously, a dynamic group scheme is more flexible and efficient in practical application. In addition, Hwang et al. introduce the notion of the controllable linkability. The controllable linkability allows an entity who holds a linking key to determine whether two group signatures were created by the same signer or not without revealing its identity. These security features of group signature schemes make it attractive for various applications, such as, privacy-preserving, data mining, anonymous online communications and so on.

With the different functionalities and levels of efficiency, a variety of group signature schemes have been presented in the last two decades [4-13]. However, very few schemes allows one to add members to the group and revoke membership with time, while they satisfy all security features, including anonymity, traceability, non-frameability. For example, Boneh et al. [14] presented a group signature system using bilinear maps. Their scheme not only provides the very short signature but also allows group manager to revoke members. However, their scheme requires the trusted party to generate the private key in the party performing setup. Since the trusted party knows the signing keys of all members, the non-frameability is not guaranteed. Furthermore, if the trusted party be removed after the setup, a new user can not be added to group. To resolve this issue, Delerable et al. proposed dynamic group signature scheme [15]. In this scheme, based on XDH assumptions, the non-frameability is achieved and the size of signature is shorter. However, using their open key, the opening algorithm is non-available when key update by revocation is considered. Obviously, this issue limits their scheme practical application. Others, such as, Benoit Libert et al. [18] presented scalable revocable group signature schemes. In these schemes, a new user can't be added to group and the size of signature is still quite big compared with short group signatures [14,15].

Very recently, Hwang [16,17] proposed a short dynamic group signature scheme. Their scheme allows one to add members to the group and revoke membership, while it satisfy the anonymity, traceability and non-frameability. Furthermore, their scheme support a very useful functionality, namely the controllable linkability. The controllable linkability allows an entity who holds a linking key to determine whether two group signatures were created by the same signer or not without revealing its identity. Moreover, in their scheme, the signature length is very short. Therefore, their scheme is brilliant. However, in [16], the opening algorithm can't determine the signer's identity since issuer may provide more than one members with a “y”. Therefore, in their scheme, the judging is indispensable to determine the signer's identity. In addition, a limitation of their scheme is that the cost of update key is expensive. Furthermore, the signature of upk should have been added to registry, otherwise the members of group may be framed by an issuer.

Therefore, how to design more efficient and flexible group signature scheme supporting anonymity, traceability, non-frameability and controllable linkability is significance research work which has obtained more attention.

1.1 Our Contributions

Motivated by the issues discussed above, we present an new dynamic group signature scheme. It allows a new user to join the group and supports membership revocation. Compared with previous related works, our scheme has several advantages as follows.

Firstly, our scheme can achieve many desirable features, such as user dynamic joining and revocation, anonymity, traceability, especially non-frameability and controllable linkability. To the best of our knowledge, only few schemes [16,17] can achieve these features. Therefore, our scheme is more flexible solution in practical application.

Secondly, our scheme is more effective. Compared with [16,17], our scheme have lower cost of signing, verifying and updating-key. Particularly, in our scheme, to update his own key, an unrevoked member only needs to compute one multi-exponentiation with two bases while one multi-exponentiation with four bases in their scheme when one user is revoked. In addition, in our scheme, both the size of group public key and member's private key are shorter than that [16].

Lastly, in our scheme, the opening algorithm can determine the identity of signer without judging while preserving the non-frameability. In [16], the judging is indispensable, otherwise a member may be framed by the issuer. Therefore, our scheme is simpler to track the identity of signer.

 

2. Preliminaries

2.1 Dynamic Group Signature Schemes

The model of dynamic group signature was introduced by Bellare et al. [3] (for short BSZ). We describe a slight variant of dynamic group signature in a form suitable for our paper, since our scheme can support membership revocation that is not a part of the BSZ model.

Here, suppose there exists a fully trusted authority (example PKI) separated from the group environment. Both a user Ui and the group manager (GM) have obtained their certificate of keys from a fully trusted authority before setting up the system. Ui's certificate is denoted by (PKUID[i], SKUID[i]), and PKUID[i] stored in the registration table Reg. The GM certificate is denoted by (PKGID, SKGID). In addition, the group manager and users are involved in our dynamic group signature without the trusted party. Specifically, our dynamic group signature scheme (DGS) consists of a tuple polynomial-time algorithms DGS=( Gkg, Join, Gsig, Gvf, Open, Grev). There algorithms are defined as follows [3]:

Gkg: Given security parameter n, it generates Gpk and Gmsk, where Gpk and Gmsk are the public key and the private key of GM, respectively.

Join: By this algorithm, Ui can co-ordinating his private key Uski with GM. Finally, the group manager adds an Reg[i] corresponding to Ui to the registration table Reg.

Gsig: Given a message M, it takes the Gpk and Ui's privacy key Uski and outputs a signature σ on a message M.

Gvf: This algorithm takes the Gpk, message M and the signature σ corresponding to M as input, output accept if the signature comes from a legitimate member of the group and reject otherwise.

Open: This takes the valid signature σ, Gmsk and the Reg as input, and outputs the identity of σ's signer.

Grev: It takes the Gpk, a Reg[i] and Gmsk as input, and generates revocation list RL. Unrevoked members update their private keys with RL. So, a group membership can be selectively disabled without affecting the signing ability of unrevoked members.

2.2 Notions of Correctness and Security

According to the model of Bellare et al. in [3], a dynamic group signature scheme must satisfy the correctness and three security requirements: anonymity, traceability and non-frameability. Now, we show these definitions with slightly differences for suitable our scheme. In the following experiments, the F is polynomial-time adversary and all of oracles are specified in [3] (including AddU(.), CrptU(.), SndTol(.), SndToU(.), USK(.), RReg(.), WReg(.), GSig(.), Ch(.), Open(.)). Let HU be the lists of honest, CU be the lists of corrupted users, GSet be the set of message-signature pairs.

1. Correctness To DGS, any F , and security parameter n, the correctness experiment is as follows.

(Gpk, Gmsk)←Gkg(n, N); HU ← ϕ ; CU ← ϕ ; (i, M) ← F (Gpk: AddU(.), RReg(.));

If i ∉ HU, return 0; If Uski= ε, return 0;

σi ← Gsig(M, Gpk, Usk[i]); If Gvf(σi, M, Gpk )=0, return 1;

j ← Open(Gpk, Gmsk, Reg, M, σi) and j ≠ i, return 1;

Let , then we claim that the DGS is correct if

2. Anonymity To any F , security parameter n and b ← {0,1}, the anonymity experiment is as follows.

(Gpk, Gmsk)← Gkg(n, N); HU ← ϕ; CU ← ϕ; GSet ← ϕ;

d ← F ( Gpk, Gmsk(issue key): Chb(M*, i0, i1), SndToU(.), WReg(.), USK(.), CrptU(.)) Return d;

Let , then we claim that the DGS is CPA-anonymous if is negligible function.

3. Traceability To any F , and security parameter n, the traceability experiment is as follows.

(Gpk, Gmsk) ← Gkg(n, N); HU ← ϕ, CU ← ϕ;

(M*, σb) ← F ( Gpk, Gmsk(open key): SndTol(.), AddU(.), RReg(.), USK(.), CrptU(.));

If Gvf( M*, σ* )=0, return 0;

If Open(Gmsk, M*, σ*) failed then return 1, else return 0;

Let , then we claim that the DGS is traceable if is negligible function.

4. Non-frameability To any F , and security parameter n, the non-frameability experiment is as follows.

(Gpk, Gmsk, Usk) ← Gkg(n, N); HU ← ϕ, CU ← ϕ;

(M, σi) ← F ( Gpk, Gmsk: SndToU(.), WReg(.),GSig(.) , CrptU(.),USK(.));

If Gvf(Gpk, M, σi)=0, return 0;

If Open(Gpk, Gmsk, M, σi)=i (i ∈ {1,…, N}) and F did not query Usk[i] or Gsig(i, M ) then return 1 else return 0.

Let , then we claim that the DGS is non-frameability if is negligible function.

2.2. Bilinear Map on Group

Let G1, G2 , GT be multiplicative cyclic groups of prime order p. The groups are defined in certain families of nonsupersingular elliptic curves which are defined by Miyaji et al. in [19]. In G1, the size of the elements is 171-bit, and that discrete log on G1 has identical difficulty with discrete log in Zq where q is 1020 bits. Let g1 ∈ G1 be generator, while g2 ∈ G2 be generator. Let φ(g2) = g1, where φ : G2 → G1 is a computable isomorphism.

Next, we review the notion of bilinear maps. Let e : G1 × G2 → GT be a map on G1, G2 , GT with three properties.

(1) Bilinearity: ∀ η ∈ G1, ∀ π ∈ G2 and a, b ∈ Z, e(ηa, πb) = e(η, π)ab.

(2) Non-degeneracy: e(g1, g2) ≠ 1GT .

(3) Computability: for all η ∈ G1, π ∈ G2, then a e(η, π) can be efficient computed.

In the next content, we always suppose that (G1, G2) are a bilinear group pair as above.

2.3. The Main Assumptions

Let g1 , g2 , G1 , G2 be defined as above, where possibly G1=G2. Now, we review the q-SDH problem. Consider the following problem: The q-SDH problem [14] in (G1, G2) is that given (q+2)-tuple , find a pair

The q-SDH Assumption is defined as a difficult problem to be solved q-SDH problem.

As a natural extension of q-SDH problem, we introduce the extended q-SDH problem and new complexity problem. Consider the following problems:

The Extended q-SDH Problem (q-eSDH). Given tuple , find a tuple and β = γk (k ≠ 0,1).

Formally, an algorithm F has advantage ε in solving q-eSDH problem if

where the probability is over the random choices of generator g2 ∈ G2 (with φ(g2) → g1), of and of the random bits of F .

Proof: Obviously, if an algorithm F can be used to solve q-eSDH problem, two q-eSDH tuples can be obtained. According to the two tuples, we can compute: . So F can obtain a q-SDH tuple

Definition 1. The (q,t,ε)-eSDH assumption holds in (G1, G2) states if no t-time algorithm has at least ε advantage in solving the q-eSDH problem.

New Complexity Problem (q-NC) Take g1, g2, G1 , G2 as above, the q-NC problem is defined as given tuple , compute

An algorithm F has ε advantage in solving q-NC problem if

where the probability is over the random choices of generator g2 ∈ G2, of

Remark: 1. we emphasize that γ and β are unknown to the algorithm F .

2. According to q-SDH assumption, cannot be obtained from cannot be obtained by . So the q-NC assumption is reasonable model to consider.

Definition 2. The (q,t,ε)-NC assumption holds in (G1, G2) states if no t-time algorithm has at least ε advantage in solving the q-NC problem.

Lemma 1 If the q-NC assumption holds, given tuple for any , it is difficult to compute

Proof: Given the known condition, if an algorithm F is able to compute , then we obtain . As a result, is calculated.

The Decision Linear Diffie-Hellman Assumption (LA) [14] Let G1 be defined as above. Let η, π, τ ∈ G1 be arbitrary generators of G1 and a, b, c ∈ Zp, the LA holds is that given η, π, τ, ηa, πb, τc ∈ G1, it is difficult to decide whether a+b is equal to c. More formally, based on the coin tosses, an algorithm F chooses uniformly random the parameters. Then, the advantage of probability of F in deciding a decision linear problem on G1 is Adv = |Adv1 − Adv2|, where Adv1=Pr[( η , π , τ ηa , πb τa+b )=yes; η , π , τ ←G1, a, b←Zp] and Adv2 =Pr[ ( η , π , τ ηa , πb , µ )=yes; η , π , µ ←G1, a, b←Zp] .

Definition 3. The (t,ε)-LA holds if no t-time algorithm has at least ε advantage in solving decision linear problem.

Linear Encryption (LE)[14] Based on the LA, the LE scheme can be obtained. Specifically, take G1's generators η , π , τ as the public key, then the corresponding private key is such that ηλ1 = πλ2 = τ . If F wishes to send a message M ∈ G1 to B, then randomly selects ξ1 , ξ2 ∈ Zp , computes ηξ1 , πξ2 , M⋅τξ1+ξ2 , and outputs the ciphertext (C1, C2, C3)=( ηξ1 , πξ2 , M⋅τξ1+ξ2 ) where η , π , τ are B 's public key. To decrypt the ciphertext, B computes with his private key λ1, λ2. Similar to prove ElGamal's security, we can show that if the LA holds, LE is also against a chosen-plaintext attack.

 

3. A ZK Protocol For eSDH

A zero-knowledge (ZK) protocol is a proof protocol with the following qualities.

The first, a verifier, after having been convinced the validity of what is proved, cannot have learned the knowledge possessed by the prover in order to conduct the proof; The second, after the protocol terminates, any other third party cannot see any meaningful thing which has taken place between the prover and the verifier. The ZK protocol is described as follows.

Let (P, V) be ZK protocol, where P is a prover and V is a verifier. In the general process of interactive zero-knowledge proof, the P commits some values to the V. After the V received, a challenge value be sent to the P. The last, the V verifies the values responded by P to decide whether P possesses some knowledge.

In group signature scheme, a verifier has been convinced the validity of signature without learning the identity of signer. Therefore, the process for verifying group signature is essentially a process of zero-knowledge proof.

3.1 ZKP-eSDH

In this section, based on q-eSDH problem, we construct a zero-knowledge protocol (ZKP-eSDH).

Let P be a prover, and V be a verifier. In this protocol, P can prove that he possesses a solution to the q-eSDH problem to V.

Setup: Generate the public values g1 , η , π , τ ∈ G1 and g2 , ω1 , ω2 ∈ G2. Here g2 is a random generator of G2 such that φ(g2) = g1 , for some γ , β ∈ Zp. η, π, τ are randomly selected in G1. A prover P possesses a tuple (R, x, y), where and x, y ∈ Zp such that

P Commit: P chooses ξ1, ξ2 and rξ, rx, ry, rδ1, rδ2 at random from Zp. Take (R, x, y) as input, P computes the following values:

P sends (C1, C2, C3, D1, D2, D3) to verifier V.

V Challenge: V sends a challenge value c chosen uniformly at random from ZZp.

P Reply: P computes vξ = rξ - c(ξ1 + ξ2) , vx = rx + cx , vy = ry + cy , vδ1 = rδ1 + cxξ1 , vδ2 = rδ2 + cxξ2 and replies B with these values.

V Verify: V computes the following five values: , D'3= e(C3,g2)vx ⋅ e(τ,ω1)vξ ⋅ e(τ,g2)-vδ1-vδ2 ⋅ e(g1,g2)vy ⋅ e(C3,ω1)c ⋅ e(g1,ω2)-c .

V accepts if Di=D'i holds (i=1,2,3).

Next, we show that ZKP-eSDH has following features:

(1) If P is honest, then he can always be accepted by V (completeness);

(2) The prover's transcript can be simulated (zero-knowledge);

(3) There exists an extractor for protocol.

Feature 1. The ZKP-eSDH is complete.

Proof: If V is honest, he can correctly recover Di=D'i (i=1,2,3) with the challenge value c and vξ, vx, vy, vδ1, vδ2. Specifically, V can computes the values:

In addition, he can also compute:

Because D3=e(C3,g2)rx ⋅ e(τ,ω1)rξ ⋅ e(τ,g2)−rδ1−rδ2 ⋅ e(g1,g2)ry , and

So , the completeness of ZKP-eSDH is proved.

Feature 2. If the LA holds and verifier V is honest , then the transcripts of ZKP-eSDH can be perfectly simulated.

Proof: Suppose, X is the distribution of the transcript output by the simulator. If the simulator succeeds, then the X is indistinguishable from the distribution of the transcript output by any actual prover under the LA on G1.

Firstly, the simulator randomly selects R ∈ G1 and and computes C1=ηξ1 , C2=πξ2 , C3=R ⋅ τξ1+ξ2. In this simulation, to compute Di=D'i (i=1,2,3), the simulator does not need to know R, x, y, ξ1, ξ2, so the pre-specified (C1, C2, C3) can also be used. By the method of simulation of proof transcript, when (C1, C2, C3) are the ciphertext LE of some R, the simulator can obtain simulation of the rest of proof transcript. After a challenge value c and vξ, vx, vy, vδ1, vδ2 are randomly selected from Zp, the simulator compute the values:

So, the simulator can output (C1, C2, C3, D1, D2, D3, vξ, vx, vy, vδ1, vδ2). Obviously, these values satisfy verification equations and are indistinguishable with the proof transcripts of ZKP-eSDH on distribution if the LA holds.

Feature 3. Extraction is feasible for ZKP-eSDH.

Proof: Now we show that the extractor can obtain a tuple q-eSDH if F can be rewind in ZKP-eSDH above to the point before he receives a challenge c. At the beginning of the protocol, A sends (C1, C2, C3, D1, D2, D3) to B. Then, to challenge c, F replies with (vξ, vx, vy, vδ1, vδ2). In this way, to challenge c′ ≠ c, F replies with . If F is convincing, all verification equations Di (i=1, 2, 3) hold for each set of values. For convenience, denote Δc = c − c′ , Δvξ = vξ - v'ξ , and similarly for Δvξ, Δvx, Δvy, Δvδ1, Δvδ2. Let , Since the values of D1 and D2 remain the same, the following equations are obtained: , from D3 expression, we can deduce:

is a q-eSDH tuple.

Since (C1, C2, C3, D1, D2, D3) are equal to the challenge value c′ ≠ c. In fact, we already know: Δvξ = Δrξ + Δcξ, Δvx =Δrx + Δcx , Δvy = Δry + Δcy .

For the same Ci(i=1,2,3) and Di((i=1,2,3) in two running, it is easy to see that Δrξ = 0 , Δrx = 0 , Δry = 0, then ξ′ = ξ , x′ = x , y′ = y .

As a result, the R' in this q-eSDH tuple is identical to R in the LE (C1, C2, C3) .

Putting the proof of three properties together, then the following theorem has been proved.

Theorem The ZKP-eSDH is an honest-verifier zero-knowledge proof of knowledge of an eSDH tuple under the LA.

 

4. Our Dynamic Group Signature Scheme from eSDH

4.1 Our Signature Scheme from eSDH

In this section, we propose a new dynamic group signature scheme. Roughly speaking, in our scheme, a signer who possess a valid q-eSDH tuple can generate a group signature which are the transcript of ZKP-eSDH protocol. Therefore, armed with theorem, we obtain from ZKP-eSDH protocol a regular signature scheme secure in the random oracle model by applying the Fiat-Shamir heuristic [20]. In our scheme, a hash function H : {0,1}* → Zp be employed. Suppose further the LA assumption holds on G1, the q-eSDH assumption and the q-NC assumption hold on (G1, G2). Now we describe our group signature as follows. To simplify, our group signature scheme is denoted by eSDH-DGSS.

Setup: Takes φ and (G1, G2) as the section 2, let H : {0,1}* → Zp is an ideal hash function, treated as a random oracle in the proof of security.

Gkg: Randomly selected a generator g2 ∈ G2, , let g1 = φ(g2). GM selects private values and computes . Let τ ← G1╲{1G1} , η , π ∈ G1, such that ηλ1 = πλ2 = τ . This algorithm generates Gpk=(g1, g2, η, π, τ, ω1, ω2) and Gmsk=(γ, λ1, λ2, ζ0). Here ζ0 is assumed initially to be 1.

Join: Ui can be added to the group after running this algorithm between GM and Ui. The GM add an item Reg[i] to the Reg.

1. Selecting a secret value , Ui computes to GM.

2. GM selects xi ∈ Zp and computes to Ui, where

3. Ui sends Si to GM, where Si is the signature of with SKUID[i].

4. Using PKUID[i], GM verifies Si. If Si is a valid signature, then GM sends xi to Ui.

As a result, Ui obtains his private key . GM adds an which is corresponding to Ui to the registration table Reg.

Gsig: Given message M, Ui chooses random ξ1 , ξ2 , rξ , rx , ry , rδ1 , rδ2 from Zp and computes the following values with his private key Uski=(Ri, xi, yi): C1=ηξ1 , C2=πξ2 , C3=Ri⋅τξ1+ξ2 , , D3=e(C3,g2)rx⋅e(τ,ω1)rξ⋅e(τ,g2)-rδ1-rδ2⋅e(g1,g2)ry , and the value of hash c=H(M, C1,C2, C3, D1, D2, D3). He also computes:

At the end, Ui generates a group signature: σ=(C1, C2, C3, c, vξ, vx, vy, vδ1, vδ2), and sends (σ, M) to the verifier.

Gvf: Given Gpk and (σ, M), a verifier verify that σ is a valid signature as follows:

If c' =c accepts and reject otherwise.

Open: To trace a signature's signer, GM takes the signature of M σ=(C1, C2, C3, c, vξ , vx , vy , vδ1, vδ2), together with Gpk and Gmsk as input, and do the following:

1. Verify the signature σ is correct on M.

2. Take elements (C1, C2, C3) of σ, and obtain someone Ri from

GM finds the index i with respect to Ri in the registration table Reg.

3. If the user index i is corresponding to in Reg and the validity of Si on Ri is validated by GM, then the algorithm claims that the group member with identity i produced σ. It provides a proof of this claim with GM which verifies the validity of signature Si on Ri with PKUID[i].

4.2 Revocation

Now we give procedure that users can be revoked by the GM in the eSDH group signature above. Given Gpk=(g1, g2, η, π, τ, ω1, ω2 ), where , η , π , τ ∈ G1. The private key of Ui is a tuple Uski=(Ri, xi, yi).

Update Key If GM have revoked users j1,⋯, jr that are corresponding to their index.

The revocation algorithm consists of three sub-algorithms, Update-Gmsk, Update-Gpk and Update-Usk which update a group public key and a user signature key, respectively.

Update-Gmsk: Updates Gmsk=(γ , λ1 , λ2 , ζ0)→(γ , λ1 , λ2 , ζr), where

Update-Gpk: Let initial Gpk=(g1, g2, η, π, τ, ω1, ω2). Using new Gmsk=(γ , λ1 , λ2 , ζr), GM updates Gpk to Gpkr=(g1r, g2r, ηr, πr, τr, ω1r, ω2r ), where , ηr = η , πr = π , τr = τ ,

GM generate the revocation list RL that containing all revoked users (let in order of revoked). Specifically, RL is defined as , Where

For (k=1,…,r), GM publishes the RL and the new public key. The RL and the new public key are given to all signers and verifiers in the system

Update-Usk: Given tuple (Gpk, RL), Ui is able to obtain his new Usk corresponding to the new Gpkr locally if he has not been revoked. However, revoked users cannot do so.

Let private key , Ui compute:

Let . Ui can compute his new private key

In fact, if a revoked user is able to update his private key, then he can execute update procedure as above. This means that revoked user's xj is not equal to xjm (m=1,…,r), contradicting xj ∈ {xjm;m=1,…,r}

Update-Open When key update by revocation is considered, GM trace a signature's signer as follows. Given updated signature σr=(M, C1, C2, C3, c, vξ, vx, vy, vδ1, vδ2), GM compute: . GM finds the index i with respect to Ri in the registration table Reg. Obviously, only GM can generate the correct ζr and RL in the opening and the revocation mechanism above. So this revocation mechanism can overcome the problem [14] that someone can fool a verifier.

4.3 Obtain Controllable Linkability

The controllable linkability of group signatures enables an entity who has a linking key to find whether or not two group signatures were generated by the same signer, while preserving the anonymity. In our scheme, the controllable linkability can also be easy to achieve as follows. Let (L1,L2) = ((ω2)λ1, (ω2)λ2) is linking key. Given two valid pairs of signatures and messages, (σ′,M′) and (σ′′,M′′), proceed as follows:

If T1=T2 then output 1, otherwise output 0. Obviously, anyone can verify whether or not two group signatures were generated by the same signer if he holds the linkability key.

 

5. Our Scheme Security

In this section, we proof the security of ours scheme. Here, we relax the full-anonymity requirement. While we follow a slightly weaker security model CPA-fully-Anonymity given in [14]. Given G1 and G2, we know that bilinear map evaluation, exponentiation and sampling are constant-time. To simplify the details of addition terms in size bound or time bounds, we use the big-O notation in the next content. To prove the security of our scheme (eSDH-DGSS) as above, we also need to the forking lemma (see [21]).

Theorem 5.1 Our scheme (eSDH-DGSS) is correct.

Proof: Let Gpk=(g1, g2, η, π, τ, ω1, ω2) be the public key, and Uski=(Ri, xi, yi) be the user's private key. The is always true, so (Ri, xi, yi) is an q-eSDH tuple. According ZKP-eSDH protocol, a correct signature σ is a part transcript of the ZKP-eSDH. One can easily show that a correct σ will always pass validation of the verifier. Furthermore, (C1, C2, C3)=( ηξ1 , πξ2 , Ri⋅τξ1+ξ2 ) in signature σ are a random LE of Ri with the public key (η, π, τ), thus these values can always be restored by the GM holding the private key (λ1, λ2). So each of the valid σ which is output by an honest signer will be correctly opened.

Theorem 5.2 If the LE is (t′,ε′)-semantically secure on G1, our scheme (eSDH-DGSS) is (t,qH,ε)-CPA-fully-anonymous, where t = t′ - qHO(1) and ε = ε′ . Here qH is the number of hash function inquiries made by the adversary

Proof: If an algorithm F can (t,qH,ε)-break the anonymity of eSDH-DGSS, we are able to construct an algorithm B in t + qHO(1)-time that can break the semantic security of LE with at least ε. Next, we give the procedure to construct the B as follows:

Assuming B possesses an LE public key (η, π, τ). Calling the Gkg, B can obtain the g1 , g2 , ω1 , ω2 . Then F is equipped with the Gpk=(g1, g2, η, π, τ, ω1, ω2) generated by B , while a user is equipped with a Uski=(Ri, xi, yi). When the hash oracle H is asked by F , B reply with elements chosen uniformly at random from Zp, ensuring to reply identically when the same inquiry is occurs.

Given a message M, i0 and i1, F accepts its fully-anonymity test. While B accepts its indistinguishability test by offering the LE of the two user's private keys Ri0 and Ri1. Now, suppose B is given an LE of Rib (C1, C2, C3), where the LE challenger chooses b equal to 0 or 1. Using (C1, C2, C3) , B generates from this LE a complete transcript (C1, C2, C3, D1, D2, D3, c, vξ , vx , vy , vδ1 , vδ2) with the simulator of feature.2. Because the tuple (C1, C2, C3) are the ciphertext (LE) of Rib, the rest of this transcript is identical distribution with in a real ZKP-eSDH, where a prover's private R is Rib. Obviously, given (C1, C2, C3), even though B does not know ξ1, ξ2, x and y, the simulator can generate a trace.

Then B patches H at (M, C1, C2, C3, D1, D2, D3) to equal c. B proclaims failure and exit if a collision occurred. Otherwise, it returns a correct signature: σ ← (C1, C2, C3, c, vξ , vx , vy , vδ1 , vδ2) to B. In the light of the definition of H, we know that the probability of emerging a collision is negligible.

Finally, a b' is output by F . B replies its own challenge with the b'. Since the part (C1, C2, C3) of the group signature is obtained from a random LE of Rib of user ib, B replies its own challenge rightly whenever F does.

As mentioned above, we know that the Gpk and the replies to F 's inquiries are all correct and accurately distributed. So B succeeds in distinguishing the LE (C1, C2, C3) with identical advantage ε if F can succeed to break the anonymity of the σ with advantage ε.

Suppose each hash query can be answered in constant time, and there are at most qH F 's queries. Then B 's running time exceeds F 's by the amount it takes to answer F 's queries. As result, B runs in time t + qHO(1) .

CPA-Fully-traceability Follow the fully-traceability [3] security notion, there are two cases breaking fully-traceability. One case is the adversary provides a correct signature σ such that the honest GM cannot trace the signer. The other case is the GM believes the origin of signature has been identified but he cannot provide a correct proof of its claim.

Suppose, there is a list of tuple (Ri, xi, yi) for index i=1,..,n, where n is the number of the members of the group. For each i, either (Ri, xi, yi) is an eSDH tuple , or else (xi*, yi*) = ?, indicating that the (xi*, yi*) corresponding to Ri* is not known. In accordance with the fully-traceability notion, then an algorithm F that breaks the full-traceability of the group signature scheme needs to complete the following work. It outputs a forged group signature σ on a message M.

Then F is successful if σ is trace to some R* ∉ {R1,…, Rn} or R* = Ri* for i* with (xi*, yi*) = ?

To prove the fully-traceability of eSDH-DGSS, the following theorem needs to be proved. With the same as above, the number of F inquiries signature oracle is denoted by qS, while the number of F inquiries hash oracle is denoted by qH.

Theorem 5.3. If both q-NC and q-eSDH are (q,t′,ε′) -difficult on (G1,G2) , our scheme(eSDH-DGSS) is (t,qH,qS,n,ε) -fully-traceable, where , t = Θ(1)t′ and n =q − k1 is the number of members of the group.

Proof: Suppose F is the algorithm that can break the full-traceability of eSDH-DGSS. The algorithm B replies F 's inquiries as oracle. B can obtain a eSDH solution if F can break the full-traceability.

Firstly, we describe the follow preparatory work needs to be completed by B .

Setup: Given groups (G1, G2) as above, a list of tuples (Ri, xi, yi) for index i=1,…,n, and generators g1, g2 such that g1 = φ(g2). Also given , B picks a generator τ ← G1╲{1G1} and values , then computes η , π ∈ G1 such that ηλ1 = πλ2 = τ . It generates the polynomial with (Ri, xi, yi), where ρ0, ρ1,…, ρn-1 ∈ Zp are the coefficients of the polynomial p(z).

Given a eSDH instance on g1, g2, B can compute . Let . Moreover, if (xi*, yi*) ≠ ? , then can be obtained with (Ri, xi, yi). Let , where t0 , t1 ,…, tn−2 ∈ Zp are the coefficient of the polynomial ti(z) . With t0 , t1 ,…, tn−2 ∈ Zp , we compute:

For the tuple (R'i, (xi*, yi*) = ?) at random index i* filled with Ri ← G1 and (xi* , yi*) ← (*, *), where (*, *) are placeholder values. So, B obtains a list of distinct new (R'i, xi, yi).

Secondly, we construct a framework for algorithm B interacting with F that wins the full-traceability game. Algorithm B sends and the open key to algorithm F . In the process, algorithm B replies F 's inquiries as random oracle. According to [3], F 's attack capabilities are modeled by accessing the following oracles.

Hash Queries: When F asks the hash of (M, C1, C2, C3, D1, D2, D3), B replies with a random element of Zp, ensuring to reply identically when the same query is occurred.

Signature Queries: Algorithm F inquires a signature on message M at index i*.

If (xi*, yi*) = ? , B randomly chooses and Ri ∈ G1, let C1=ηξ1 , C2=πξ2 , C3=Ri⋅τξ1+ξ2 , and calls simulator with the values C1, C2, C3. The simulator returns a transcript ZKP-eSDH (C1, C2, C3, D1, D2, D3, c, vξ , vx , vy , vδ1 , vδ2) . Then B obtains a group signature σ=( C1, C2, C3, c, vξ , vx , vy , vδ1 , vδ2). In addition, it patches the H at (M, C1, C2, C3, D1, D2, D3) to equal c. If B previously sets the oracle at this point to some other c′, it declares failure and exits. Otherwise, it returns σ to F .

If (xi*, yi*) ≠ ?, B generates a signature σ on M with key by running the signing procedure, and returns σ to F .

Private Key Queries: Algorithm F asks for the private key of user at some i (xi*, yi*) ≠ ?, B returns to F . Otherwise, B declares failure and exits.

Output: At the end, when F succeeds, it outputs a forged signature σ=( C1, C2, C3, c, vξ , vx , vy , vδ1 , vδ2) on a message M. B open σ with the key (λ1, λ2) and obtains someone R* ∉ {R'1,…, R'n} or and (xi*, yi*)=? at random index i*.

1. If R* ∉ {R'1,…, R'n}, then the probability of breaking fully-traceability is the probability of successfully forged the group signature.

2. If and (xi*, yi*)=?, at random index i* and F never queries the private key oracle at i*, but there exist a forged group signature that traces to , then the probability of breaking fully-traceability is equals to ε/n, where ε and 1/n are the probability of successfully forged signature and the probability of i* selected , respectively.

From F 's view, the i* is independent. With qs << qH << p, we show the probability that B fails and F succeeds is negligible. In simulated signing queries, besides the message M, the hash oracle takes nine elements of bilinear group pair as input, so (qs+ qH) qs／p9 is the upper bound of the probability of collision. In fact, it is negligible.

Now we show that how to obtain two related group signatures with the forking lemma [21]. Denote signature as (M , σ1 , c , σ2), where σ1 =( C1, C2, C3, D1, D2, D3) and σ2 = (vξ , vx , vy , vδ1 , vδ2). c is derived from the random oracle H by inputting σ1 and M. In the above process, let F be a forger (of either type) with probability ε′.

Next, we show the procedure that B obtains another eSDH tuple with the results of F 's success, and obtains contradicting the eSDH assumption. Apply the methodology of the forking lemma, we obtain the following procedure.

The interaction between F and B is fully depicted by the random string θ used by F and B , and by the vector Γ of replies made by the oracle of H. Let S be the collection of pairs (θ ; h) that enable B succeed with forgery ( M , σ1 , c , σ2 ) by calling F . In the circumstances, let ind(θ ; Φ) be the index of Γ at which F inquiries (M, σ1). We define v = Pr[S] = ε′ - (1/p) , where the 1/p is the probability that F guessed the hash of (M, σ1) without any help. As above, denote Sj (1 ≤ j ≤ qH) be the collection of pairs (θ ; h) such that ind(θ ; Γ)=j, denote J be the collection consisting of the most likely Index j such that J = {j|Pr[Sj|S]}≥1/(2qH) , then Pr[ind(θ, Γ)|S]≥1/2 .

Let Γj denote the restriction of Γ index strictly less than i. Since Pr[Si]≥v/(2qH) , there exist a subset Ωj such that ∀(θ ; Γ) ∈ Ωj , PrΓ′[(θ , Γ′) ∈ Sj, Γ′ = Γ]≥(4qH) , Pr[Γj|Sj]>1/2 . it shows that Pr[∃j ∈ J : Ωj ∩ Sj]≥1/4 with a simple reasoning processes.

If B replays F many times, with fixed θ but randomly chosen Γ′ such that . The B succeeds and obtains a forgery (M, σ1, c, σ2). It derives from Ωj for some j∈J an execution (θ ; Φ) such that

When F and B are rewound to the jth inquiry, and go on with an oracle Γ′ (Γ′ ≠ Γ) from the jth item, then B succeeded at a second forgery with (M, σ1) still inquiries at F 's j-th hash inquiry with probability at least v/(4qH) .

Thirdly, we know that there exists an extractor for two signatures. By using the extractor, B obtains a n-eSDH tuple from (M, σ1, c, σ2). and

According to the Feature3, the is identical with the in the LE (C1, C2, C3) in σ1. B proclaims success only when the extracted eSDH tuples is not amongst those that B created.

Following by the technique of lemma [21], compute:

Because for all i, then . Otherwise, B obtains new tuple for some i. According to the lemma1 , this will lead to conflict with the q-NC. So r≠0, B can compute: . Algorithm B obtains a new eSDH tuple , contradicting the eSDH assumption. Putting all together, the following claim has been proved.

There exists a B that solve an instance of n-eSDH with probability (ε - 1/p)2 / (16qH) or (ε / n - 1/p)2 / (16qH) in time O(1)⋅t if the forger F successfully break the fully-traceable with probability ε.

Next, we prove that our scheme can achieve the non-frameability.

Theorem 5.4. If the discrete logarithm problem (DLP) is difficult on G1, our scheme (eSDH-DGSS) is non-frameability.

Proof: Suppose the error probability Open is negligible. We only consider that there exists an algorithm F that can break the non-frameability of eSDH-DGSS. Now we show how to construct an algorithm B that breaks the DLP on G1.

Let (Ri, xi, yi) be the private key of user i. We show that B can solve the DLP on G1 if F can frame user i. F frames user i means that F can generate a signature which traces to Ri.

Setup: Given private key (Ri, xi, yi) (j≠i, j=1,…,n) of members group, the private key of GM (γ , λ1 , λ2) and all user's Reg[j] (including Reg[j]), B responds F 's queries as oracle. F is given Gpk=(g1, g2, η , π , τ , ω1 , ω2). We describe the interactive process between F and B.

Hash Queries: F inquires the hash of (M, C1, C2, C3, D1, D2, D3), B replies with an element random selected from Zp, ensuring to reply identically when the same inquiry is occurs.

Signature Queries: F can query the signing oracle by at index j (j≠i).

Private Key Queries: F queries for Uskj of the user at index j (j≠i).

Reg Queries: F queries for the Reg[j] of the user at any index j in the registration table. F forged σ=( C1, C2, C3, c, vξ , vx , vy , vδ1 , vδ2) that traces to Ri is output with probability ε when F succeeds. Replay this process, on the basis of the forking lemma, B can obtain with probability ε2 / (16qH) , where qH is the number of hash queries made by F . Moreover, using the extractor, one can find the whole private key of user i (Ri, xi, yi). With yj be obtained and contained Reg[j], so DLP on G1 be successfully solved by B .

 

6. Performance Analysis

Next, we analyze the performance of our scheme in terms of features, keys size and computation overhead. This analysis includes a comparison between a few best-known group signature schemes [15-18].

6.1 Performance Analysis

With the families of curves described in [19], the size of elements of G1 is l =171-bit, the size of c is 80-bit and the order bit-length of G1 is taken as a lG =170-bit prime, as a result the total length of the signature is 1443-bit. When given parameters as above, we obtain the security is identical with a level 1024-bit RSA signature. We also assume that the non-frameability, adding a member in group, controllable linkability, the size of group public key, the size of user's key and the signature size are denoted by NF, ADD, CL, GPKS, USKS, SS, respectively. The comparison results of features, keys size (for Gpk, Usk) and signature length are summarized in the following table.1.

Table 1.A Comparison of Some Group Signature Schemes

From the Table 1, it shows that [16,17] and our scheme have the all desirable features (including dynamic joining and revocation, anonymity, traceability, non-frameability and controllable linkability). However, compared with [16,17], the Gpk and Usk size are shorter in our scheme.

Furthermore, in our scheme, the computation costs for signing, verifying, opening, key-updating are as follows.

Signing: Since e(C3,g2) = e(τ,g2)ξ1+ξ2 ⋅ e(R,g2) , by caching e(τ,g2) and e(R,g2), signing does not need the pairing operation. Furthermore, C1=ηξ1 and D1=ηξ1rx-rδ1 can be computed by one exponentiation ηmax{ξ1,ξ1rx-rδ1} (similarly, C2 and D2 can be computed), signing only need three exponentiations in G1, one multi-exponentiation with four bases in GT. For multi-exponentiation, all bases are fixed in signing, further speedup by precomputation is possible.

Verifying: A verifier can obtain e(C3,g2)vx e(C3,ω1)c by computing . Therefore, verifying requires two multi-exponentiations with two bases in G1, one multi-exponentiations with two bases in G2, one multi-exponentiation with four bases in GT and one pairing operation.

Opening: Since , opening requires one multi-exponentiation with two bases in G1.

Key-updating: All unrevoked users must update their private keys when a new revocation occurs. When one user revoked, this updating requires one multi-exponentiation with two bases in G1.

The computation cost of signing, verifying, and user's key-updating are denoted by SC, VC and UC, respectively. In additional, let TEw,h denotes simultaneous multi-exponentiation using w elements of group Gh, where h=1, 2, T. Let P denotes simultaneous pairing operation. The comparison results of computation costs for signing, verifying, updating-key are summarized in the following Table 2.

Table 2.A Comparison of Some Group Signature Schemes

In Table 2, it shows that our scheme has lower computation costs for signing, verifying, updating-key. Therefore, our scheme is more efficient. Particularly, comparing with [16] which use expensive pairing operations (in judging process) to determine a signer's identity, our scheme is more attractive because we don't need pairing operation.

6.2 Experimental Results

The test for these results was performed on an Pentium Dual-Core CPU E5400 clocked at 2.70GHz and RAM 1.96GB. This test makes use of three D-type curves from the PBC library [22] running on top of Gnu GMP on Windows XP.

Every test result is the average of 1,000 tests. In Table 3, we show the running time of signing, verifying, user’s key-updating (with 1 revoked user), opening. According to [23], further speedup is possible, when this test was performed on A-type curves.

Table 3.Experimental Results (time:ms)

For the sake of space, we only show the parameters for D174 Curve in Table 4.

Table 4.The D174 Curve with the embedding degree k = 6

 

7. Conclusion

In this paper we proposed dynamic group signature. In our scheme, the non-frameability is guaranteed without the trusted party. Compared with the contemporary counterparts, our scheme more efficient and flexible group signature scheme which support the non-frameability. Furthermore, our scheme can also easily achieve the controllable linking which introduced by Hwang et. al. In addition, our scheme has provided algorithm structure such that the opening algorithm is available when key update by revocation is considered without incurring other secure threats. Lastly, the group manager flexibility allows one member to add to the group and revoke membership with time in our scheme. However, in [14], the adding member can't be achieved.