Informatica 34 (2010) 189-237 189
On the Security of Two Group Signature Schemes with Forward Security
Kitae Kim
Department of Mathematics, and
ISRL, Graduate School of IT&T, Inha University, Republic of Korea ktkim@inha.ac.kr
Ikkwon Yie
Department of Mathematics, Inha University, Republic of Korea ikyie@inha.ac.kr
Daehun Nyang
ISRL, Graduate School of IT&T, Inha University, Republic of Korea nyang@inha.ac.kr
Keywords: digital signature, group signature, forward security, cryptanalysis Received: September 22, 2008
A group signature scheme allows a group member of a group to sign messages on behalf of the group anonymously. In case of dispute, a special entity of the group, group manager, can reveal the signer of a valid group signature. In 2005, Zhang et al. proposed a new group signature with forward security based on their earlier scheme in ICICS 2003. Recently, Zhou et al. proposed a dynamic group signature scheme with forward security at GCC 2007, In the year of 2008, Zhang and Geung pointed out the scheme is insecure and suggested an improvement. In this paper, we analyze a security analysis of Zhang et al.'s group signature scheme and Zhou et al.'s group signature scheme. We also discuss why the improved Zhou et al.'s scheme by Zhang et al. is still insecure.
Povzetek: Analizirane so varnostiskupinskega podpisovanja dveh modelov: Zhou in Zhang.
1 Introduction
Following the first work by Chaum and van Heyst (10) in the year of 1991, many group signature schemes have been proposed and analyzed. In such a scheme, individual members of a group is allowed to sign messages on behalf of the group anonymously. Moreover, group signature schemes allow the group manager to reveal a signer's identity in case of dispute. Unforgeability, anonymity and traceability were noted as basic security requirements for group signature schemes by Chaum and van Heyst (10). Later, more security requirements such as unlinkability, collision-resistance, exculpability, and framing have been introduced. Informally, a secure group signature scheme must satisfy the following properties :
Unforgeability : Without knowledge of the secret key(s), no one can generate a valid group signatures. In other words, only the group members can sign messages on behalf of the group.
Anonymity : Anybody except the group manager has no information of the member's secret keys. Particularly, given a valid group signature, no one except the group manager can identify the signer.
Unlinkability : Even though seeing a list of signatures, anyone except the group manager can not relate two signatures together as being produced by the same member.
Traceability : It is not possible to produce signatures which can not be traced to one of the group that has produced the signature. That is, for given a group signature, the group manager is always able to determine who is the signer of the signature.
Exculpability : Neither member of the group nor the group manager can produce signatures on behalf of other group members. Sometimes, the requirement is used in a weaker form that group members except the group manager can not produce a valid signature that traced to other member of the group.
Coalition Resistance : Even though a set of group members collude together, it is not possible to generate signatures that cannot be traced to any of them. A weaker form that a set of members cannot produce a signature that is traced to other member than the set is sometimes called Framing.
In 2003, Zhang et al. (15) proposed a group signature scheme with forward security. However, G. Wang showed
238 Informatica 34 (2010) 237-242
K. Kim et al.
that Zhang et al.'s scheme is insecure by presenting several attacks (14). After that, Zhang et al. suggested a new group signature scheme in (16) and claimed that their scheme satisfies all the above requirements, and, in addition to, forward security.
Recently, Zhou et al. (17) proposed a dynamic group signature scheme with forward security. But, Zhang and Geng showed that the Zhou et al.'s scheme is universally forgeable and suggested an improvement in (18). The authors claimed that their improvement can be proved to be secure without presenting the details of the proof.
In this paper, we analyze the Zhang et al.'s new group signature scheme in (16) and the improvement of Zhou et al's group signature scheme (as well as the original Zhou et al.'s scheme). More precisely, we point out the open algorithm of new Zhang et al.'s scheme does not properly operate, and show their scheme is not secure even if the algorithm can be improved. In addition, we show that the Zhou et al.'s scheme and its improvement are insecure.
2 Zhang et al.'s Group Signature Scheme
Before presenting Zhang et al.'s group signature scheme, we briefly review some notions used in the scheme.
For a positive integer n, the Euler phi function (or Euler totient function) $(n) is defined to be the number of positive integers less then n which are relatively prime to n. If a positive integer n is a composite of two primes, say n = pq, then $(n) = (p — 1)(q — 1).
As RSA-like schemes, their group signature scheme is constructed on the group Z*, where Z* = {k :0 < k < n and gcd(k, n) = 1}. Due to the security, n is usually chosen to be a product of two strong primes of the same size. A prime p is called strong prime if (p — 1)/2 is also prime. To summarize, n is chosen to be n = p1p2 such that pi and p2 are large strong primes of the same size.
Additionally, two cryptographic primitives, a hash function and a signature of knowledge, are used in Zhang et al.'s group signature scheme. More precisely, it employs a coalition resistant hash function h( ), and a signature of knowledge SPK on the discrete logarithm : Given g and y = gY for some 7, SPK{7 : y = gY}() is a (non-interactive) proof of knowledge of 7
2.1 The Scheme
We briefly describe Zhang et al.'s new group signature scheme (16).
Setup. The group manager (GM) randomly chooses two strong primes p1,p2. Let n = p1p2 and G =< g > be a cyclic subgroup of Z*. GM chooses an integer x as his secret key, and computes the public key y = gx mod n. GM selects a random integer e such that gcd(e, $(n)) = 1 and computes
d such that de =1 mod $(n). The expected system life-time is divided into T intervals which are publicly known. Finally, GM publishes the public
key (y,n,g,e,h(-),IDGM,T), where IDGm e Z* is the identity of the group manager and (c, s) =
SPK{7 : y = gY}().
Join. If a user, say Bob, wants to join to the group, Bob executes an interactive protocol with GM as follows :
1. Bob chooses a random k e Z*
as his private
k
key, and computes his identity IDB = gk mod n. Then he generates (c, s) = SPK{7 : IDb = gk}(). Finally, Bob keeps k privately and sends (IDB, (c, s)) to the group manager.
2. Upon receiving (IDB, (c, s)), GM verifies the signature of knowledge (c, s). If the verification holds, GM choose a random a e Z* and computes a triple (rB ,sB, WBo) from
rB
SB
WB0
= ga mod n,
= a + tb x,
= (IDgm tb IDb )-dT mod n.
Then GM sends Bob (sB ,rB ,wBo) via a private channel, and stores (IDB, (c,s)) together with (rB ,sB ,wBo) in his local database.
3. After Bob receives (sB ,rB ,wBo), he verifies
gSB =
tb y
IDgm IDb Tb =
mod n mod n
(1) (2)
If the equations (1) and (2) hold, Bob stores (sB ,tb , wBo) as his initial membership certificate.
Evolve. Assume that Bob has the group membership certificate (sB,tb,wBj) at time period j. Then at time period j +1, he updates his group membership certificate as (sB ,tb ,wBj+1) by computing
WBj+1 = (WBjY mod n,
_dT -j
where wBj = (tbIDGmIDb ) mod n.
Sign. Suppose that Bob has the group membership certificate (sB ,tb ,wBj) at time period j. To sign a message m, Bob chooses random numbers qi,q2,q3 € Z*, and computes
T — j
zi = gqi yq2 q3e mod n, u = h(zi,m), T2 = q3wBä mod n, ri = qi + (sB + k)u, T3 = q2 - tBu.
The resulting group signature on m is a =
(u, ri, T2 ,T3, m,j).
T
— e
w
o
ON THE SECURITY OF TWO GROUP SIGNATURE SCHEMES.
Informatica 34 (2010) 237-242 239
Verify. Given a = (u,r1,r2,r3,m,j), a verifier computes
T — i
z'i = IDugmgri rl yr3 mod n, ?
and then checks u' = h(z'l ,m). If so, the verifier accepts the signature as a valid group signature from a legal group member.
Open. In case of a dispute, GM can open signature to reveal the actual identity of the signer. If a =
(u, r1,r2,r3, m,j) is a valid signature, GM operates as follows to find the signer's identity :
1. Computes n = u-1 mod $(ri).
2. Compute
IDugm9ri r2 ~ yr3 mod n.
2.2.1 Incorrectness of the open algorithm
Suppose that a = (u, r1,r2,r3, m, j) is a valid group signature signed by Bob with valid certificate (sB ,rB ,wBj ). Then since
T —j
z1 = gqi yq2 qf mod n
Tj
= IDUmgri re yr3 mod n,
T — j
we have grZ1yr3 = IDGMr2 (mod n), and so
zi gri yr
dT—j
= IDGdM j r2 mod n	(5)
= IDGM—j q3wUB, mod n. (6)
On the other hand,
r2	-u—1 A
—^ = r2w- mod n
WB j	Bj
3. Find wB using (IDB,rB,wBo) in his local database satisfying
?	dT — j
r2/wr>B = (z'/griyr3) mod n.
Revoke. Suppose GM wants to revoke Bob's membership certificate at time period j. Then GM performs as follows:
1.	Compute Rj = wB (rBIDB )dT j mod n.
2.	Publish (Rj ,j) in the certificate revocation list (CRL).
Given a valid signature a = (u, ri, r2, r3, m, j), a verifier can identify whether a is produce by a revoked member. For this sake, he performs as follows :
1. Compute
= q3wB - wBu mod n.
(7)
(8)
We can easily see the quantities (6) and (8) are not
,T — j	— 1
the same : If these are equal then IDGdM = w-u (mod n). Powering ueT-j on both sides we have IDUM = IDgmIDbrB (mod n), which leads to a contradiction.
Remark 2.1. Before the invention of the above scheme, Zhang et al. already proposed a group signature scheme (15) entitled with "A novel group signature scheme with forward security" in ICICS 2003. At the same time, Wang suggested several attacks against the scheme (14). Lately, Zhang et al. proposed a new group signature scheme described above. Considering Zhang et al.'s early scheme, the following modification is seemed to be natural :
Given a valid group signature a = (u, ri,r2, r3, m,j), the group manager does the following :
z[ = IDUmgrir2 yr'3 mod n (3) 1. Compute n = u 1 mod ^(n).
2. Check
T — j ?
z\ (r-1R) = gri yr3 mod n (4)
If the signature satisfies the equation of (3) and (4) then the verifier concludes that the signature is revoked.
2.2 Security Analysis of Zhang et al.'s Scheme
In (16), Zhang et al. analyzed the security of their scheme, and concluded that their scheme satisfies the security requirements of group signature schemes. However, we find the open algorithm is incorrectly designed. Moreover, their scheme does not satisfy the unforgeability even if one can improve the open algorithm to work correctly.
2.	Compute z ' = IDUMgri r2 3 yr3 mod n.
3.	Find (sB,rB ,wBj ,IDB) in his local database satisfying
'2
WB-
z
gri y
IDbrB (mod n).
However, this modification is not a correct improvement. Indeed, for a valid signature a = (u,ri,r2,r3,m, j), every (wBj, ID B ,rB) (not necessarily membership certificate of actual signer) satisfies the equation of 3.
2.2.2 Forgery attack
The above subsection illustrates that the open algorithm of Zhang et al.'s group signature scheme does not correctly work. Of course, there might be an improvement of the
z
T j
e
n
n
240 Informatica 34 (2010) 237-242
K. Kim et al.
open algorithm while we couldn't find such one. However, we can break the scheme even if the algorithm can be modified to operate correctly. We remark that the attack in subsection is much similar to Wang's attack (14). Now, we describe our attack which can be mounted by anyone, not necessarily a group member.
Suppose that a group member Bob with certificate (rB ,sB ,wBj) was revoked by GM at time period j. Then the CRL should contain (Rj ,j) where Rj = wBj (rBIDb )d . Now an attacker Oscar (not a group member, outsider) can sign on any message M chosen by himself as follows:
1.	Choose qi, q2, q3, a, ft £ Z*.
2.	Compute
zi u
r2
ri r3
T — j
gqi yq2 q3 mod n, h(z1,M ),
Rug-ay?q3 mod n q1 + aeT-j mod n,
q2
— jSeT j mod n.
In order to show that the tuple (u,r1,r2,r3, M, j) is a valid group signature, it is enough to show that zi = z1, where
z1
T —j
gqi yq2 q3 mod n,
z1 = IDUm gri re2
mod
We first note that
Rj
wBj (rBIDb )dT ° mod n
(rB IDb IDgm )-
dT-j
IDgm mod n.
dT 3 (rBIDb)dT j mod n
Then
Tj
= IDUmgri rl yr3 mod n = IDUmgri (RUg-aypq3)|T—3 yr3 mod n
T j	T j	T j
= ID UGM gqi+ae RGe g-ae
■ y?eT—3 qf—3 yq2-?eT—3 mod n
ID gm ID g m
-dT 3 '
T — j
• 9qi yq2 qe m°d n
T — j
= gqi yq2 q3e mod n =
Thus, once the GM releases a revocation token (Rj,j) for a group member at time period j, everyone can generate valid group signatures during the same time period on any message. Since Ri = Rf 3, one can compute Ri for all i > j from the token Rj and then mount the above attack. Therefore, one can generate valid signatures for any time period i where i > j.
3 Zhou et al.'s Group Signature Scheme
At GCC 2007, Zhou et al. proposed a dynamic group signature with forward security (17). Later, Zhang and Geung (18) showed the scheme is insecure by presenting a universal forgery attack, and proposed an improvement. However, we find that the improvement as well as the original scheme is insecure.
3.1 Brief Review of Zhou et al.'s Scheme
We first briefly describe the Zhou et al.'s group signature scheme in (17) as follows:
Setup. Let Fq be a finite field, E : y2 = x3 + ax + b be an elliptic curve over the field , where q is a prime of n bits and 4a3 + 27b2 mod q = 0, and P £ E(Fq) be a (base) point whose order is a large prime number l. Let #E (Fq) and ^ denote the order of the elliptic curve and a function which makes the conversion from a point P = (x, y) £ E(Fq) to x, respectively. We use (P)x instead of ^(P). Now, the group manager GM chooses a random kGM £ Z* and then computes Kqm = kGMP as its public key. The GM's secret key is kGM, and the group public key is KGM. We assume that each user B has its identity IDB which is an element of E(Fq).
Join. When a user B wants to join the group, GM and B perform the following protocol :
1.	B chooses a random kB £ Z* as private key, and computes KB = kB P as private key. Then B sends (KB, IDB) to the group manager.
2.	Upon receiving (KB ,IDB), GM chooses a random uB £ Z*, and computes ID'B = h(uB\\(IDb)x)P. Then he sends ID'B to the GM.
3.	GM selects a random v £ Z*, and computes VB = vP and
sb = kGMh((IDB)x\\(Vb)x) + v mod l.
GM sends (VB ,sb ) to the user B, and stores (IDB, ID'b ,uB) in his local data base.
Finally, B gets its membership certificate (Kb ,ID'b ,Vb ,sb ) and becomes a member of the group.
Sign. To sign a message m £ Z*, a member B chooses a random r £ Z* , and computes
R = rP,
I
(kB — m(R)x)r 1 mod l, IDB + idb + kB kgm .
Then a = (m,s,R,I, KB ) is a group signature on the message m.
y
z
T-j
s
ON THE SECURITY OF TWO GROUP SIGNATURE SCHEMES.
Informatica 34 (2010) 237-242 241
Verify. A verifier accepts a signature a = (M, al,a2,a3, a4) if the following equations are satisfied
sb P = h((ID'B )x\\(Vb )x )Kgm + Vb ,
?
a 4 = a\a2 + m(a2)xP-
Note that the verifier must be able to search ( sb ,Vb ) corresponding to a4 = KB. That is, this algorithm assumes that tuples (sb ,Vb ,Kb ) of all group members are public.
Open. Omitted (see (17))
3.2 A Comment on Zhou et al.'s Scheme and on its improvement by Zhang et al.
Zhang et al. (18) pointed out that Zhou et al.'s scheme is forgeable, and presented an improvement by including another hash function H(■) : {0,1}* x E(Fq) ^ Z* and revising the Sign and Verify algorithms. In particular, the revised Sign procedure is as follows:
To sign message m, a member B randomly selects r e Z* to compute
R = rP,
s = (kB - H(m,R)(R)x)r— mod l,
I = IDB + IDb + kB kgm .
Then the group signature on m is a = (m, s, R, I, KB).
Though Zhang et al. claimed that their improved scheme is proved to be secure without detailed proofs, this revision as well as the Zhou et al.'s scheme is obviously linkable since two same pieces of information I and KB are included in all group signatures generated by the same group member.
To avoid the linkability property, the deterministic information depending on the actual signer should be randomized. In this case, however, the group manager cannot trace the actual signer because the information I is used by the group manager in opening process. In other words, the Open algorithm cannot properly operate. Even worse, since Kb is critical value for signatures generated by B to be verified, no one can verify the signatures if the information is randomized. As a result, we conclude that the Zhou et al.'s scheme as well as Zhang et al.'s improvement cannot be repaired.
4 Conclusion
Zhang et al.'s new group signature scheme described in section 2 is based on their earlier version in (15). The earlier scheme was analyzed by Wang (14) and Cao (9), but no attack against the later scheme was announced. In this paper, we firstly presented security analysis of Zhang et al.'s new group signature scheme. By our analysis, the open algorithm of their scheme is incorrectly designed. Moreover,
the scheme is not secure even though the open algorithm can be improved. Finally, we analyze Zhou et al.'s group signature scheme (17) and an improved scheme (18). The Zhou et al.'s scheme and the improved scheme are always linkable because each signature in the schemes includes deterministic values corresponding to a group member.
Acknowledgement
The authors would like to thank anonymous reviewers for their valuable comments. This work was supported by the IT R&D program of MIC/IITA,[2008-F-036- 01,Develop-ment of Anonymity-based u-Knowledge Security Technology].
References
[1]	G. Ateniese, J. Camenisch, M. Joye, G. Tsudik (2000), A practical and provably secure coalition-resistant group signature scheme, CRYPTO'00, LNCS 1880, Springer-Verlag, pp. 255-270.
[2]	J.H. An, Y. Dodis, T. Rabin (2002), On the security of joint signature and encryption, EUROCRYPT'02, LNCS 2332, Springer-Verlag, pp. 83-107.
[3]	G. Ateniese, B. de Medeiros (2003), Efficient group signatures without trapdoors, ASIACRYPT'03, LNCS 2894, Springer-Verlag, pp. 246-268.
[4]	M. Bellare, D. Micciancio, B. Warinschi (2003), Foundations of group signatures : Formal definitions, simplified requirements and a construction based on general assumptions, EUROCRYPT'03, LNCS 2656, Springer-Verlag, pp. 614-629.
[5]	D. Boneh, X. Boyen, H. Shacham (2004), Short group signatures, CRYPTO'04, LNCS 3152, SpringerVerlag, pp. 45-55.
[6]	X. Boyen, B. Waters (2006), Compact group signatures without random oracles, EUROCRYPT'06, LNCS 4004, Springer-Verlag, pp. 427-444.
[7]	J. Camenisch and A. Lysyanskaya (2002), Dynamic accumulators and application to efficient revocation of anonymous credentials, CRYPTO'02, LNCS 2442, Springer-Verlag, pp. 61-76.
[8]	J. Camenisch and M. Stadler (1997), Efficent group signature schemes for large groups, CRYPTO'97, LNCS 1294, Springer-Verlag, pp. 410-424.
[9]	Z. Cao (2005), Untraceability of Two Group signature Schemes, Cryptology ePrint archive, http://eprint.iacr.org/2005/055.
[10] D. Chaum, E.V. Heyst (1992), Group signatures, EU-ROCRYPT'91, LNCS 547, Springer-Verlag, pp. 257265.
242 Informatica 34 (2010) 237-242
K. Kim et al.
[11]	H. Park, S. Lim, I. Yie, K. Kim, J. Song (2009), Strong unforgeability in group signature schemes, to apper in Elsevier.
[12]	D.X. Song (2001), Practical forward secure group signature schemes, Proc. of the 8th ACM CCS 2001, ACM press, pp. 225-234.
[13]	G. Tsudik and S. Xu (2003), Accumulating composites and improved group signing, ASIACRYPT 2003, LNCS 2894, Springer-Verlag, pp. 269-286.
[14]	G. Wang (2003), On the security of a Group Signature with Forward Security, ICISC 2003, LNCS 2971, Springer-Verlag, pp. 27-39.
[15]	J. Zhang, Q. Wu and Y. Wang (2003), A Novel Efficient Group Signature With Forward Security, ICICS 2003, LNCS 2836, Springer-Verlag, pp. 292-300.
[16]	J. Zhang, Q. Wu and Y. Wang (2005), A New Efficient Group Signature With Forward Security, Informatica, Vol. 29, No. 3, Slovenian Society Informatika, pp. 321-325.
[17]	X. Zhou, X. Yang, P. Wei and Y. Hu (2007), Dynamic group signature with forward security and its application, Proc. of the 6th International Conference on Grid and Cooperative Computing (GCC 2007), IEEE Compupter Society, pp. 473-480.
[18]	J. Zhang and Q. Geng (2008), On the Security of Group Signature Scheme and Designated Verifier Signature Scheme, Proc. of International Conference on Networking, Architecture, and Storage, IEEE Computer Society, pp. 351-358.