Two Group Signature Schemes with Multiple Strategies Based on Bilinear Pairings

Published Online October 2009 in MECS

In 1991, group signature was introduced by Chaum and van Heyst[1] . Compare to traditional single signature, in the group signature scheme, a signer can sign a message on the behalf of the group without revealing his identity, receiver can verify the validity of a signature with group public key, verify whether a signature was signed by a group member or not, but don’t know who generated this signature. In addition, it is difficult to determine whether two different signatures were generated by a same group member or not. Anyone (even if group manager) can not forge a valid group member’s signature. From this work, a variety of the group signature scheme has been proposed with many improvements by some scholars such as J.Camenish and M.Stadler[2], J.Camenish and M.Michels[3], G.Ateniese and G.Tsudik[4 ,5]. Especially, the two group schemes proposed by J.Camenish and M.Stadler in [2] in which the group public key and the length are independent to numbers of group members, are very meaningful for the development of signature technology.

At present, to group signature scheme practicability research, following aspects research continuously attract domestic and foreign scholar’s attention widely:

( 1 ) Group member revocation. Once a group member is dropped from group, its signatures will be regarded as

Manuscript received January 17, 2009; revised August 21, 2009; accepted September 18, 2009.

invalid. As a practical group signature scheme, it should permit member to join and quit dynamically. In the existing schemes, the technology to join a group effectively is quite mature. But in member's revocation aspect, although many researches have been conducted, the contribution is not quite ideal, and part of schemes has even been proven to contain some mistakes later on.

( 2 ) Forward secure. If a member's signature key was leaked out, then his whole signatures (the past and the future) would be leaked out. A complementary approach is to reduce the potential damage in case secrets are exposed. In what is often called forward security, the main idea is to ensure that secrets are used only for short time periods, and that compromise the effective range of a secret does not affect anything based on secrets from prior time periods. One of the challenges in designing such a system is to be able to change secret information without the inconvenience of changing public information, such as the public key.

( 3 ) Ahead signature prohibition. A group member can only sign a message on the behalf of the group only after he joins that very group, and can not sign a signature of which the signing time is prior to the time he joins group. In a security group scheme, it is very necessary to prohibit ahead signature.

The concept of forward secure signatures was first proposed by Anderson in [6]. Once the secret key was leaked out, forward security scheme can minimize the influence to the system security, the group signature generated previously remained valid and do not need to be re-signed. The commonly used method is to divide system time into T periods, the signing key evolve over time, a group member’s signing key can evolves from SK_i to SK_{i + 1} using a public one-way function. Initially Anderson used forward security only for traditional single signature, from this work, this concept was applied gradually in group signature scheme ^[11-13], meanwhile widely applied to other kind of signature scheme ^[14].

Up to now, although many scholars have made many related research in the forward security for group signature scheme. But almost all schemes are based on the strong RSA, simultaneously are continuous to use the method in [6] that the system time was divided into T periods, while the period evolve over period T, system has to be initialized and all member's signing keys have to be assigned again. Moreover there is no scheme that can prohibit the ahead signature efficiently.

In Asiacrypt2001, Boneh et al. proposed a short signature scheme [7]. Using the bilinear pairing algorithm based on hyper-elliptic curves, the length of signature was shortened to 170 bits opposite to 1024 bits in the RSA algorithm, 320 bits in DSA algorithm. Security of scheme was founded by Gap Diffie-Hellman[8,9] group. The short signature which has the obvious superiority in the network transmission, attract scholars' attention widely. In recent years, many signature schemes based on the bilinear pairing were proposed, however since DDH is easy to be solved in bilinear pairing, there are few group signature scheme based on the bilinear pairing, more often than not, these schemes are designed for identity-based signature [7,10]. In [15], two group signature schemes based on the bilinear pairing are proposed in which an on-line third party, called security mediator (SEM) is introduced. Unfortunately, in these two schemes, a group member can not verify the signing key received from group manager (GM) and SEM, and there is possibility that SEM can obtain a group member’s signing key by collaborating with any other group member while SEM is no longer credible. Meanwhile, in order to realize the traceability, all signature messages must be stored by SEM, which cause huge memory burden to SEM. What is more, there is a drawback in these two schemes discovered by Cheng et al in [15], in which a dishonest group member may generate a signature to satisfy verification condition, but SEM can not open it correctly[16]. Then Cheng et al proposed a improved scheme which satisfy traceability In [16]. Vo et al proposed a forward security signature scheme from bilinear pairing, however their scheme is a traditional single signature, his design method is not suitable to group signature.

By now, there is no group signature scheme based on bilinear pairing and equip with forward security be proposed. In summary, for the group signature based on bilinear pairing, there are several common drawbacks as follows:

• ( 1 )    The group member can not verify the signing key received from GM and SEM while he joins the group;

• ( 2 )    In order to open signatures, SEM has to store all signature messages, that result much memory costs to SEM;

• ( 3 )    There is no forward security.

In 1989, Desmedt and frankel proposed the concept of threshold group signature through combining group signature and secret sharing together[17] . Following this research, many threshold group schemes were proposed by scholars. In now days some bilinear pairings based threshold group signature schemes were proposed, but there are various flaws in their schemes. In [18], a Chameleon threshold signature based on bilinear pairing was proposed, in this scheme, TTP (Trusted Three Party) can generate any threshold group signature even if there are no sub-signature and scheme is not completeness, there are same designing flaws in scheme proposed in

• [19] . In [20], a forward secure threshold group signature scheme was proposed in which changing member’s private key will cost huge times from a time period to next and a revoked member can still participate in sign and times cost will become bigger and bigger while time period increment.

In this paper, a group signature scheme based on bilinear pairing and a threshold group signature scheme based on bilinear pairing were proposed. There are multiple security strategies in these two schemes, every member can verify the signing key received from GM and SEM when he joins group, meanwhile, these schemes supports the group member revocation, and have the traceability where SEM has not to store any signature messages. Even if GM or SEM cannot obtain a group member’s signing key by collaborate with any other group member. In the group signature scheme, forward security is proposed for the first time, the scheme has forward security with unlimited time periods, meanwhile, ahead signature generated by a group member can be prevented efficiently. In threshold group signature scheme, there is forward security with no necessary to maintain time periods in first time.

Our paper is organized as follows. Section П describes the definition and security requirements of a group signature scheme with forward security. We propose a new forward security group signature scheme with multiple forward security strategies. Section Ш describes the definition and security requirements of a threshold group signature scheme with forward security. We propose a new threshold forward security group signature scheme with multiple forward security strategies, and describe the analysis of security and complexity. Finally we give our conclusion in section IV.

• II. G ROUP S IGNATURE

• A.    Security Group Signature Scheme

A security group signature scheme consists of following procedures.

• (    1 ) SETUP. A probabilistic procedure, on input a security parameter, outputs the system parameters, the group public key and the secret key for GM and SEM.

• ( 2 )    JOIN. When a user want to join the group, the group manager and the user execute a protocol interactively. The user receives the signing key and becomes a new group member.

• ( 3    ) EVOLVE. Given input of a group member’s signing key for time period i, this procedure outputs the corresponding group member’s signing key for time period i + 1.

• ( 4 )    SIGN. Given input of a group member’s signing key, a message m and a time period i, this probabilistic procedure outputs a signature on message m.

• ( 5 )    VERIFY. Given input of a group public key, a group signature on a time period i, a message m, this procedure verifies whether signature is a valid on m signed with a group member’s signing key of time period i.

• ( 6 )    OPEN. Given input of a valid group signature on the message m, a GM’s or SEM’s secret key, this procedure determines the identity of the signer for the group signature.

A group signature scheme should satisfy the following security requirements:

• (    1 ) Correctness. Signatures produced by a group member using SIGN must be accepted by VERIFY.

• ( 2 )    Unforgeability. Only group members are able to sign messages on behalf of the group.

• ( 3 )    Anonymity. Given a valid signature of a message, it is computationally hard for everybody but the GM or SEM to identify the actual signer.

• ( 4 )    Unlinkability. Unless to open signatures, it is computationally hard for anybody but the GM or SEM to decide whether two different valid signatures were generated by the same group member or not.

• (    5 ) Exculpability. Neither a coalition of group members nor the group manager can generate a valid signature that will be opened by the OPEN procedure as generated from another group member.

• ( 6 )    Traceability. GM or SEM can always open a valid signature using the OPEN procedure and identify the actual signer.

• B.    The Proposed Scheme

Setup: There are three kind roles in group, first is group administrator (GM), second is a set of group member and third is trusted on-line third party, called a security mediator (SEM). First GM selects x e Z q * as his private key and compute

X = xP as his public key, defines two cryptographic hash functions:

H 1 : Z q * ^ G 1 and

H ₂:{0,1} * ^ Z q * .

{ G 1 , G ₂, eq , P , Y , H 1 , H 2 } be published as the group public messages. SEM selects s e Z q * as his private key and computes

S = sP as his public key. In initial, GM sets time period to 1.

Join: Suppose that user u, with identifier IDi e Zq* is a user who wants to join the group in time period j. GM computes y = H1( ID)

as ui 's public key, and computes x = x -1 yt, sends xi as a signing sub-key to ui secretly. ui can believes that the xi received from GM is a signing subkey after verified the correctness of xi by equation

• 3 Y , x ) = H ( P , y^ .

Meanwhile SEM selects a random number e, e Z * for iq ui and saves pair(ei, yi) secretly. SEM computes si,j = serjyi and j e P, then sends si, as another signing sub-key and vi, as verification factor to ui secretly. ui can verifies the correctness of si, received from SEM by equation:

• < ( v j ^s i,j ) = ^{H ( S} , y i -D

After the correctness of x_i and s_{i , j} are verified, user u_i become a group member and save the pair ( x_i , s_{i , j} ) as his signing key for time period j.

Revoke: In scheme, there is a Certificate Revocation List (CRL) which record the information of revoked group members, the item of CRL is ( y_i , t ) means a group member with public key y_i was revoked in time period t.

Evolve: While time periods evolve from j to j + 1 , Group member u_i ’s signing key ( x_i , s_{i , j} ) be evolved to ( x i , s i j _{+ 1}) by SEM with equation

"V

• I ,    j +1 i'l °l , j

and s_{i , j} be destroyed by u_i .

Sign: To generate a group signature on message m in time period j ,Group member u_i selects a random number k e Z q , computes:

^r 1 = ky ,

CT = kH2( m || j) si ,j c = kH2(mWj)x , then sends (yi, г1,ст, c, j) to SEM secretly. Firstly, SEM checks whether signer is a valid group member by CRL, then by equation r1H2(m || j) = S-1 e/CT to verify whether si,j was used to signature, finally, compute r2 = kP r3 = s-1 eir1 r4 = s2 P + k (r + r3 + c)

( r ₁, r ₂, r ₃, r ₄, c , j ) is group member u_i ’s signature for message m in time period j .

Verification: To verify the correctness of signature ( r ₁, r ₂, r ₃, r ₄, c , j ) by equations:

( ( P , ^r 4 ) = C ( S , S ) ( ( ^r 2 , r _i ⁾ t ^{( r} 2 , ^r 3⁾ e(. ^r 2 , c )          ( 1 )

and

• C ( X , c ) = C ( P , H 2 ( mMj ) Г 1 )                    ( 2 )

Through Equation (1) to verify the signature is signed by a valid member, and signing sub-key s_{i , j} was used to signature. Then through equation (2) to verify signing sub-key x_i was used to signature.

Open: In the case of a dispute, SEM has to open a signature ( r ₁, r ₂, r ₃, c , j ) according the saved ( e_i , y_i ) . If there is a e_i satisfies equation :

ser - ^r 3 = ^r 1 , then signer is y_i .

• C. Analysis of Security and Efficiency

In the following, we will show that our proposed scheme satisfies the all security requirements of a forward security group signature.

Correctness ： In proposed scheme, when SEM received ( y, , r 1 , c , c , j ) from signer, SEM confirms if signer is a valid group member by check the CRL. If there is a ( y_k , t ) in CRL where y, = y_k and j >= t , SEM refuse ( y, , r 1 , c , c , j ) immediately, otherwise SEM continues to verify whether the signing sub-key s_{i , j} was used for signature by equation r 1 = s -1 e’a . This guarantees that ( r ₁, r ₂, r ₃, c , j ) was generated by a valid group member.

Verifier verifies whether the signature sub-key x_i was used for signature by signer with equation (2). We note that:

• ( ( X , c ) = ( ( xP , kH ₂( M ) x )

• =    < ( xP , kH ₂( M ) x -1 y )

• =    < ( xx ^{- 1} P , kH ₂( M ) y , ) = c ( P , H 2 ( M ) ky , ) = C ( P , H 2 ( M ) Г 1 )

That the verification of equation (1) and equation (2) means that signature was signed by a valid group member with signing key ( x , s _{, j} ) , signature can be accepted.

Anonymity: Given a valid signature ( r ₁, r ₂, r ₃, c , j ) , it is computationally hard to identify the actual signer because ( r ₁, r ₂, r ₃, c ) were computed with random number. Therefore anyone except SEM cannot deduce identifier of the signature .

Unlink ability: Given any two group signatures ( r ₁, r ₂, r ₃, c , j ) and ( r ₁^', r ₂^', r ₃^', c ^', j ^') , they are generated by different random number. According difficulty of DL, it is computationally infeasible to decide whether the two signatures were generated by the same group member or by different group member.

Unforgeability: Suppose that a GM wants to generate a signature, he can choose a random number k ,but because he don’t know s,, or cannot deduce s,, from c = ks,, in ,j                                                                       ,j                                          ,j a feasible algorithm, so he can’t generate a (y,.,r1,c,c, j) which can pass the verification of equation r1 = s-1e'c . Meanwhile, SEM can not forge a signature which can pass the verification of equation (2) in the reason he don’t knows x .

Coalition-resistance: Our proposed scheme can resists coalition attack efficiently, there is unnecessary to check the relations between group member’s public key like the schemes designed in [15] and [16]. Even if there are k group members their public keys satisfy relation y 1 + y ₂ + ... + y_k = y , mod q , this k group members can compute x together as follow:

x 1 + x ₂ +... + x_k = x ^{- 1} y 1 + x ^{- 1} y ₂ +... + x ^{- 1} y_k

• = x ^{- 1 (} y 1 ⁺ y 2 ⁺ ... ⁺ y k )

• =    ^x- 1 y i

=x

But they cannot compute s _{, j} , So they can only compute: r 1 = ky , , c = kH ₂( m || j ) x , , cannot compute a valid c which pass SEM’s verification. Therefore these k group members can not forge a valid signature while there is a risk of leak out their own signing sub-key.

Revocability ： In our proposed scheme, every signature is published finally by SEM, SEM verify every signature message received from group members whether the signer’s identity is valid, meanwhile verify whether the signing sub-key s ,j was used honestly by equation r1H2(m II j) = s-1 elC , this verification can be used to prevent a dishonest group member forge a untraceable signature, so the r3 generated by SEM can be regarded as the basis to open the signature.

Traceability ： With the analysis of revocability, the identity of signer can not be forged. Because only SEM knows e and ( e , y ) , therefore only SEM can open signature by se f¹ r ₃ = r 1 .

Forward security ： While time period evolves from j to j + 1 , group member u _t ’s signing key ( x , , s , j ) be evolved to ( x , , s , j _{+ 1}) where s , j _{+ 1} : = e f¹ s , j ,according to the difficulty of DL, besides SEM, every others can not derive s from s , ^ , j                    ^ , j ^{+ 1}

Ahead signature prohibit: While u joins group in time period j , he receives the signing key ( x , s _{, j} ) from GM and SEM, because he do not knows e ,he can not also derives s , j -1 from s , j ,so he can not generates a valid signature ( r 1 , r ₂, r ₃, c , j ') which satisfy j ' <  j .

Efficiency analysis ： By now, there is no group signature scheme with forward security based on bilinear pairing, therefore there is no necessary to provide a compare with other similar schemes. To enhance signing efficiency, SEM can computes s ^{- 1} and e ,j in advance. With the signing procedure, computing r 1 , c and c cost a point multiplication separately, SEM verify cost a point multiplications and the cost 4 times point multiplications to compute r ₂ , r ₃ and r ₄ , there are 9 times point multiplications in sum for generating a valid signature, 7 times computations of bilinear map and a hash compute for verify a signature. The length of a group signature is 5|P|.

To realize this scheme in environment: Pentium ( R ) 4 CPU 2.4 GHz + 512M RAM + Windows XP + VC6.0+PBC library. A point multiplication cost 32ms and a cost 64ms. Numbers of group was set to 50. A group signature was generated in 410ms, verification procedure cost 440 ms, opening a group signature cost 1050ms.

Ш . Threshold group signature

• A.    Security Threshold Group Signature Scheme

A security threshold group signature scheme consists of following procedures.

• (    1 ) SETUP. A probabilistic procedure, on input a security parameter, outputs the system parameters, the group public key and the secret key for GM and SEM.

• ( 2 )    JOIN. When a user want to join the group, the group manager and the user execute a protocol interactively. The user receives the signing key and becomes a new group member.

• ( 3 )    SIGN. Consist of two steps:

Sub-signature, a probabilistic algorithm, given input of a group member’s signing key, a message m, this procedure outputs a sub-signature on message m.

Threshold signature synthesis, a valid algorithm, given input of t members’ sub-signature on message m, this procedure outputs a threshold signature on message m.

• ( 4 )    VERIFY. Given input of a group public key, a threshold group signature, a message m, this procedure verifies whether signature is a valid on m signed with a group member’s signing key.

• ( 5 )    OPEN. Given input of a valid threshold group signature on the message m, a GM’s or SEM’s secret key, this procedure determines the identity of all t signer for the threshold group signature.

A threshold group signature scheme should satisfy the security requirements as showed in section 2.1.

• B.    The Proposed Scheme

Setup: There are three kind roles in group, first is group administrator (GM), second is a set of group member and third is trusted on-line third party, called a security mediator (SEM). Firstly GM selects x e Z q * as his private key and compute

• X = xP

as his public key, Defines two cryptographic hash functions:

H ₁:{0,1} * ^ Z q * and

H 2 : G ^ Z q ,

SEM constructs t-1 degree polynomial:

f ( x ) = a ₀ + a 1 x +... + a _t-1 x t ^-1 mod q where each a _k e Z_q and computes a check vector:

V = ( V o , V 1 , ... V _M)

for each coefficient a _k as:

V_k = a k P mod q k = 0,1,...., t -1 .

• { G 1 , G ₂, eq , P , Y , H 1 , H ₂, V } be published as the group public messages. SEM selects 5 e Z_q * as his private key and computes

S = 5P as his public key.

Join: Suppose that user u, with identifier ID, e Zq* is a user who wants to join the group. GM computes y,= f (ID) P as ui 's public key, and computes x,= xf (ID,)P , sends xi as a signing sub-key to ui secretly. ui can believes that the xi received from GM is a signing subkey after verified the correctness of xi by equation:

$y„ X ) = C ( x , P )

and y=Ek".^ID-)kVk .

Meanwhile computes

• ⁵ = ⁵У i

then sends s as another signing sub-key to u secretly. u can verifies the correctness of s received from SEM by equation

• c ( y , S ) = c ( 5 , , P ) .

After the correctness of x and s are verified, user u become a group member and save the pair ( x , s ) as his signing key.

Revoke: In proposed scheme, there is a Certificate Revocation List (CRL) which records the information of revoked group members, the item of CRL is ( ID , , т ,1 , ^ 2 ) means that a group member with identifier ID was revoked in time т ,2 and all signatures signed by this user are invalid from time т_п .

Sign: Suppose there is a group B = { u 1 , u ₂ ,... u, } needs to generate a group signature on message m ,every group member u, where ( i = 1,2,... t ) selects a random number k e Z_q ^* , computes:

Г = < ( P , P ) k , finally, t members can compute:

R = П t =1 r .

Member u can generates sub-signature:

q , = k , P + H 1 ( m 11 R ) LxP where

А = П у е B,j« (0 - ID j )/( ID , - ID j )

and sends ( m , q , y ) to SEM secretly. SEM checks whether signer is a valid group member by CRL, if the member was cancelled then refuse sub-signature immediately, otherwise SEM checks correctness of subsignature q by equation:

(qq,,P ) = r. ■ C ( H 1⁽ m || ^R ) ■ L- y_pX ) .

As soon as SEM gains t valid sub-signature on message m, Firstly SEM selects k e Z_q ^* randomly and system time stamp T, computes

K = kX and

Q i = Y u , e Bq^

Then SEM generates a identifier vector :

ID = ( ID [1], ID [2],..., ID [ t ])

with every signer’s identifier, computes:

k i = H 2 ( kQ_x + iP ) and modifies ID by equation:

ID [ i ] = k i ® ID i ] .

Finally SEM computes:

Q2 = kQi + Hi(ID || T)s2P , the threshold signature (m,R,K,Q1,Q2,T,ID) on message m be generated.

Verification: To verify the correctness of signature ( m , R , K , Q ₁, Q ₂, T , ID ) ,verifier need to searches CRL firstly, if there is a revoke record ( ID _рт 1 , т _{i 2}) which satisfies т i ₁ < T <  т _{i 2} ,a service provided by SEM are required that SEM computes kQ ₁ by

Q 2 = kQ 1 + H 1 ( ID || T ) s ² P , then computes ki' = H ₂ ( kQ + iP ) and can gets signers list by ID [ i ] = k i ® ID [ i ] . If there is a revoke record ( ID_i , T _{i 1}, T _{i 2}) which satisfies ID [ j ] = ID i ,SEM return a message YES to verifier, verifier refuses threshold signature, otherwise verifier can verifies the correctness of ( m , R , K , Q ₁, Q ₂, T , ID ) by equation:

C ( Q 1 , P ) = R ■ (V 0 , H 1 ( mU ) X )              (3)

and

« ( Q 2 ,P ) = « ( Q 1 ,K ) ■ « ( S , H 1 ( ID || T ) 5 )          (4)

Verifier accept threshold group signature while equation (3) and (4) are correctness, otherwise refuse threshold group signature.

Open: In the case of a dispute, SEM can open a signature ( m , R , K , Q ₁, Q ₂, T , ID ) .Firstly SEM can computes kQ ₁ with equation Q ₂ = kQ + H ₁( ID || T ) s ² P by his secret key s ,then computes k i = H ₂( kQ + iP ) where ( i = 1,2,... t ) , finally can determines signers list ID by ID [ i ] = k i ® ID [ i ] .

• C. Analysis of Security and Efficiency

In the following, we will show that our proposed scheme satisfies the all security requirements of a forward security threshold group signature.

Correctness ： In proposed threshold group scheme, SEM confirms if signer is a valid group member by check the CRL while SEM received ( m , R , K , Q ₁, Q ₂, T , ID ) from signer, then checks if the sub-signature was send from member u i by equation : « ( q i ,P ) = r i ■ « ( H ₁( m || R ) ■ L i ■ y i , X ) . SEM generates threshold ( m , R , K , Q ₁, Q ₂, T ) when validation of t sub-signature be checked.

The signature ( m , R , K , Q ₁, Q ₂, T , ID ) is a valid threshold group signature only if it can pass the verification of equation (3) and (4). We note correctness of equation (3) as follow:

« ( Q 1 ,P ) = « ( X _u, _e B kP + H 1 ( m || ^R ) L i X i P , P )

• =    « ( X u i _{e B} ^k i P , P ) ■ * H 1 ( mUR ) xa 0 P , P )

• =    П u i _e B (k^k i P , P ) ■ ^ a 0 P , H 1 ( m П R ) xP )

• =    R ■ C ( K o , H i ( mUR ) X )

Correctness of equation (3) be showed as follow:

« ( Q 2 , P ) = « ( kQ i + H i ( ID || T ) s ² P , P )

• =    C ( kQ i ,P ) C ( H i ( ID || T ) s ² P , P )

• =    « ( Q i , K ) ■ « ( S , H i ( IDHT ) S )

Anonymity: Given a valid threshold group signature ( m , R , K , Q 1 , Q 2 , T , ID ) , because

Q i = X u . _e B ( ^k i P + H 1 ( mUR ) L , xP )

• =    X u , e B k i P + X u , e B ^H 1 ( mH^R ) L i XP

• =    X _и, _e B k i ^{P +} xa 0 ^H 1 ^{( m} 11 ^R ) ^P

There are no information of any member in Q ₁ ; meanwhile for the other parts of signature, R and ID consist of t random number separately; K and Q ₂ were computed by random number and hash function, therefore ( m , R , K , Q ₁, Q ₂, T , ID ) is anonymity, anyone except SEM cannot deduce identifier of the signature .

Unlink ability: Given two group threshold signatures ( m , R , K , Q 1 , Q 2 , T , ID ) and ( m ', R ', K ', Q 1 ', Q 2 ', T ', ID ') , they are generated by different random number. According difficulty of DL, it is computationally infeasible to deduce the signers list from a threshold signature, meanwhile it is also in vain to compare same part of ( m , R , K , Q 1 , Q 2 , T , ID ) and ( m ', R ', K ', Q 1 ', Q 2 ', T ', ID ') . Therefore anyone besides SEM cannot decide whether the two different signatures were generated by the same group of members or by different group of members.

Traceability: In proposed threshold group scheme, because threshold group signature be generates by SEM and identifiers of all signers are stored in ID , therefore SEM can computes signers list by open algorithm using his secret key. Any others cannot open a threshold group signature.

Coalition-resistance: Our proposed scheme can resists coalition attack efficiently. when t members want to forge a threshold group signature. Although they can compute xa ₀ P by

• X    u . e B X i L = X u . e B xf ( ^ID i ) ^L i ^P

• =    xf (0) P

• =    xa ₀ P

and further forge R, but they cannot compute s ² P ,and cannot deduce s from SEM’s public key S and equation Q 2 = kQ\ + H ₁( ID || T ) s ² P due to the difficulty of DL and k is a random number, therefore they cannot forge a valid signature which is untraceable.

Forward security ： A member u_i ’s information ( ID_i, T _{i 1} , T _{i 2} ) would be recorded in CRL if u i was cancelled, u_i sub-signatures cannot be accepted by SEM no longer and the signatures he participated that signing time after т _{i 1} can pass verification no longer. But all signatures he participated that signing time before т _{i 1} are still valid.

Efficiency analysis ： With the threshold signing procedure, generating a sub-signature cost 2 times point multiplications, synthesizing t sub-signatures to a threshold group signature cost 2t times computations of bilinear map and SEM computes K,Q2 in 3 times point multiplications. In sum there are 2t + 3 times point multiplications and 2t times computations of bilinear map for generate a valid threshold signature, 5 times computations of bilinear map for verify a threshold signature. The length of a signature is 5|P|.

To realize this scheme in environment: Pentium ( R ) 4 CPU 2.4 GHz + 512M RAM + Windows XP + VC6.0+PBC library. The numbers of group was set to 50 and threshold value was set to 5. A valid threshold signature was generated in 1400ms, verification procedure cost 340 ms, opening a threshold signature cost 46ms.

• IV. Conclusion

In this paper, A group signature scheme and a threshold group signature scheme based on bilinear paring were proposed. The group signature scheme has forward security while group member’s signing key can be evolved with unlimited time periods. The threshold group signature scheme has forward security without necessary to maintain time periods in first time. Two schemes have also the function to prevent ahead signature, a group member can verify the signing key received from group GM and SEM. Anyone Even if GM or SEM cannot forge any valid group member’s signature. These two schemes support the group member revocation efficiently and have traceability.