I.

On the Security of Zhang-Wu-Wang's Forward-Secure Group Signature Scheme in ICICS'03

Ping Wang, Xiaofeng Chen, and Kwangjo Kim

International Research center for Information Security (IRIS)

Information and Communications University (ICU), Korea

Abstract

A group signature scheme allows a group member to sign messages anonymously on behalf of the group. However, in the case of a dispute, the identity of the actual signer can be revealed by a designated entity. J. Zhang, Q. Wu, and Y. Wang proposed a novel efficient group signature scheme with forward secrecy at ICICS 2003. Later, Guilin Wang pointed out this scheme is linkable, untraceable, and forgeable at ICISC 2003. Furthermore, in this paper we show that this scheme is not coalition-resistant.

Introduction

The concept of group signature was introduced by Chaum and van Heyst [1] in 1991. It allows any member of a group to sign messages anonymously on behalf of the group. The signature can also be verified by using a single group key. However, in case of a dispute, a designated group manager can reveal the signer of a valid group signature. Furthermore, any two signatures produced by the same signer are unlinkable by anyone else with the sole exception of a designated group manager. The salient features of group signatures make them attractive for many specialized applications, such as e-voting, e-bidding and e-cash system [2, 3, 4]. Many group signature schemes have been proposed after the initial work [5, 6, 7, 8, 9, 10].

The concept of forward secrecy was proposed by Ross Anderson [11] for traditional signature. In 2001, Song [12] firstly presented a practical forward secrecy group signature scheme. J. Zhang, Q. Wu, and Y. Wang [13] proposed a novel efficient group signature scheme with forward security at ICICS 2003, and as they claimed their scheme is a little more efficient than Song’s scheme. Later, Guilin Wang [14] pointed out this scheme is linkable, untraceable, and forgeable at ICISC 2003. Furthermore, in this paper we show that this scheme is not coalition-resistant, i.e., a colluding subset of group members can generate a valid group signature that can not be traced by the group manager.

The rest of this paper is organized as follows. In Section II, we will introduce the  definition of a forward-secure group signature scheme and the security properties. Section III reviews Zhang-Wu-Wang scheme. Then, our security analysis is presented in Section IV. Finally, we conclude this paper in Section V.

This work was supported by a grant No. R12-2003-004-01004-0 from the Ministry of Science and Technology, KOREA.

II.  The Model

In this section we will introduce the definition  and security properties of forward-secure group signature schemes.

Definition A forward-secure group signature scheme is comprised of the following procedures:

- SETUP: On input of a security parameter, this probabilistic algorithm outputs the initial group public key (including all system parameters) and the secret key for the group manager.

- JOIN: A protocol between the group manager and a user that results in the user becoming a new group member. The user’s output is a membership certificate and a membership secret.

- EVOLVE: An algorithm that on input a group signing key for time period j, outputs the corresponding group signing key for time period j + 1.

- SIGN: A probabilistic algorithm that on input a group public key, a membership certificate, a membership secret, and a message m outputs a group signature of m.

- VERIFY: An algorithm for establishing the validity of an alleged group signature of a message with respect to a group public key.

- OPEN: An algorithm that, given a message, a valid group signature on it, a group public key and a group manger’s secret key, determines the identity of the signer.

- REVOKE: An algorithm that on input a group member’s certificate, a group public key and the corresponding group manger’s secret key, outputs a revocation token that revokes the group member’s signing ability.

A forward-secure group signature scheme must satisfy the following security properties:

- Correctness: Signatures produced by a group member using SIGN must be accepted by VERIFY.

- Unforgeability: Only group members are able to sign messages on behalf of the group.

- Anonimity: Given a valid group signature for some message, identifying the actual signer is computationally hard for everyone but the group manager.

- Unlinkability: Deciding whether two different valid signatures were generated by the same group member is computationally hard.

- Exculpability: Neither a group member nor the group manager can sign on behalf of other group members.

- Traceability: The group manager is always able to open a valid group signature and identify the actual signer.

- Coalition-resistance: A colluding subset of group members (even if comprised of the entire group) cannot generate a valid group signature that cannot be traced by the group manager.

- Revocability: The group manager can revoke a group member’s signing ability so that this group member cannot produce a valid group signature any more after being deleted.

- Forward secrecy: When a group signing key is exposed, previously generated group signatures remain valid and do not need to be re-signed.

III.  Zhang-Wu-Wang Scheme

In this section we will briefly review Zhang-Wu-Wang scheme.

3.1 SETUP Procedure

The group manager (GM) randomly chooses two large primes p, p of the same size such that p = 2p' +1 and p = 2p'+1, where both p' and p' are also primes. Let n = pp, and G = <g> be a cyclic subgroup of Z. GM randomly chooses an integer x as his secret key, and then sets his public key as y = g mod n. GM selects a random integer e(e.g., e = 3) which satisfies gcd(e, Φ(n)) = 1, and computes d such that de = 1 mod Φ(n), where Φ(n) is the Euler Totient function. Let h(·) be a publicly known coalition-resistant hash function (e.g., SHA-1, MD5). The expected system life-time is divided into T intervals and the intervals are publicly known. (c, s) = SPK{γ : y = g}( ) denotes the signature of knowledge of logy on the empty message. Finally, the group manager publishes the public key (y, n, g, e, h(·), ID, T), where ID is the identity of the group manager.

3.2 JOIN Procedure

If a user, say Bob, wants to join the group, he executes an interactive protocol with GM. Firstly, Bob chooses a random number k ∈ Z as his secret key, and computes his identity ID = g mod n. Then, Bob generates the signature of knowledge (c, s) = SPK{γ : y = g}( ) to show that he knows a secret value k to meet ID = g mod n. Finally, Bob keeps k privately and sends (ID, (c, s)) to the group manager.

While receiving (ID, (c, s)), GM first verifies the signature of knowledge (c, s). If the verification holds, GM chooses a random number a ∈ Z, and computes as follows.

r = g mod n, s = a + rx

w = (rIDID) mod n

Then, GM sends Bob (s, r, w) via a private channel, and stores (s, r, w) together with (ID, (c, s)) in his local database.

Bob accepts (s, r, w) as his initial membership certificate if the following two equalities hold.

g = r y mod n

rIDID = w mod n

3.3 EVOLVE Procedure

Assume that Bob has the group membership certificate (s, r, w) at time period j. Then at time period j+1, he updates his group membership certificate as (s, r, w) by computing

w = (w) mod n

3.4 SIGN Procedure

Suppose that (s, r, w) be Bob’s group membership certificate at time period j. To sign a message m, Bob randomly chooses two numbers q, q ∈ Z, and computes z, u, r, r, r as follows:

z = gy mod n

u = h(z,m)

r = w mod n

r = q + (s + k) · u · h(r) (in Z)

r = q . r · u · h(r) (in Z)

The resulting group signature on m is σ = (u, r, r, r, m, j).

3.5 VERIFY Procedure

Given σ = (u, r, r, r, m, j), a verifier accepts it as a valid group signature on m if and only if u = h(z', m), where z' is computed by

z' = IDgry mod n

3.6 OPEN Procedure

Given a group signature σ = (u, r, r, r, m, j), if necessary, GM can open it to reveal the actual identity of the signer who produced the signature. GM first checks σ’s validity via VERIFY procedure. If σ is a valid signature, GM operates as follows to find the signer’s identity:

(1) Compute η = 1/(u · h(r)) mod Φ(n).

(2) Compute z' = IDgry mod n.

(3) Search his database to find a pair  (ID, r) that satisfies the following equality:

rID = (gy/z') mod n.

(4) If there is a tuple (r, ID) satisfying the above equation, GM concludes that ID is the identity of the actual signer.

3.7 REVOKE Procedure

When GM wants to revoke Bob’s membership certificate at time period j, he publishes duple (R, j) in the CRL (the Certificate Revocation List), where the value R is computed by

R = (rID) mod n

Given a valid group signature σ = (u, r, r, r, m, j), a verifier can identify whether σ is produced by a revoked group member. For this sake, he performs as follows:

(1) Compute z' = IDgry mod n.

(2) Search all (R, i) (i≤j) in CRL to check whether there is a R (i≤j) such that the following equality holds:

gy = z'(R) mod n.

(3) If one such R (i≤j) is found, the verifier concludes that the signature σ is revoked, i.e., it is generated by a group member after he is deleted.

IV.  Security analysis

In [14], Guilin Wang presented a security analysis of Zhang-Wu-Wang group signature scheme proposed in [13]. By successfully identifying several attacks, he demonstrated that this scheme is insecure. More specifically, his results show that this scheme is linkable, untraceable and forgeable.

In this section we show that this scheme is not coalition-resistant, which means that a colluding of group members, such as, Alice and Bob, can generate a valid group signature that cannot be traced by the group manager.

For simplicity, let sk = (s, r, w, ID,  k), and sk = (s, r, w, ID, k), where  w = w mod n = w mod n, and w =  w mod n = w mod n. sk and sk denote Alice's and Bob's signing key respectively at time period j.

Firstly, they can forged a valid certificate, and then they can generate valid group signature on any message using this forged certificate which also can not being traced.

They forge w, ID, k as follows:

w = IDw mod n

ID = ID ‧ g mod n

k = k - ke (in Z)

Now, we will show (s, r, w, ID, k) is a valid group membership certificate. Notice that ID = ID ‧ g mod n = g mod n = g mod n. Then we have the following equalities.

rIDID = (rIDID)g mod n

= w ‧ g mod n

= (wID) mod n

= w mod n

Now, Alice and Bob get another new valid certificate (s, r, w, ID, k) according to JOIN procedure. They can generate valid signature on any message with this certificate. When such signatures are forged, neither Alice nor Bob will be traced, because rID ≠      rID mod n. and rID ≠ rID mod n.

The above discussion shows that a colluding of two group members can generate a valid group signature that cannot be traced by the group manager. So this scheme is not coalition-resistant.

V. Concluding remarks

In this paper, we presented a further security analysis of Zhang-Wu-Wang group signature scheme proposed in [13]. More precisely, our results show that their scheme is not coalition-resistant. In fact, how to design a secure and more efficient group signature scheme is still a hot issue. The most recent investigations are given in [15, 16, 17].

References

[1]  D. Chaum and E. van Heyst. Group Signatures. In Advances in Cryptology - EUROCRYPT'91, vol. 547 of LNCS, pp. 257-265, Springer-Verlag, 1991.

[2] S. Canard and J. Traore. On fair e-cash systems based on group signature schemes. In: Information Security and Privacy (ACISP 2003), LNCS 2727, pages 237-248.

[3] G. Maitland and C. Boyd. Fair electronic cash based on a group signature scheme In: Information Security and Cryptography (ICICS'01), LNCS 2229, pages 461-465. Springer-Verlag: 2001.

[4] K. Sakurai and S. Miyazaki. An anonymous electronic bidding protocol based on a new convertible group signature scheme. In: Information Security and Privacy (ACISP'00), LNCS 1841, pages 385-399. Springer-Verlag, 2000.

[5] G. Ateniese and G. Tsudik. Some open issues and new directions in group signature schemes. In: Financial Cryptography (FC'99), LNCS 1648, pages 196-211. Springer-Verlag, 1999.

[6] G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. In: Advances in Cryptology - CRYPTO 2000, LNCS 1880, pages 255-270. Springer-Verlag, 2000.

[7] E. Bresson and J. Stern. Efficient revocation in group signatures. In: Public Key Cryptography (PKC'01), LNCS 1992, pages 190-206. Springer-Verlag, 2001.

[8] J. Camenisch and M. Stadler. Effient group signature schemes for large groups. In: Advances in Cryptology - CRYPTO'97, LNCS 1294, pages 410-424. Springer- Verlag, 1997.

[9] J. Camenisch and M. Stadler. Effient group signature schemes for large groups. In: Advances in Cryptology - CRYPTO'97, LNCS 1294, pages 410-424. Springer- Verlag, 1997.

[10] L. Chen and T. P. Pedersen. New group signature schemes. In: Advances in Cryptology - EUROCRYT'94, LNCS 950, pages 171-181. Springer-Verlag, 1995.

[11] Ross Anderson. Invited Lecture, 4th ACM Computer and Communications Security, 1997.

[12] Dawn Xiaodong Song, Practical forward secure group signature schemes. Proceedings of the 8th ACM conference on Computer and Communications Security, Pennsylvania, USA, November, pp. 225-234.

[13] J. Zhang, Q. Wu, and Y. Wang. A novel efficient group signature scheme with forward security. In: Information and Communications Security (ICICS'03), LNCS 2836, pages 292-300. Springer-Verlag, 2003.

[14] Guilin Wang. On the Security of a Group Signature Scheme with Forward Security. In: Information Security and Cryptology - ICISC 2003, LNCS 2971, pp. 27-39. Berlin: Springer-Verlag, 2004.

[15] A. Lysyanskaya, S. Micali, L. Reyzin, H. Shacham. Sequential Aggregate Signatures from Trapdoor Permutations. In: EUROCRYPT 2004, LNCS 3027, pp. 74-90. Springer-Verlag, 2004.

[16] Guilin Wang, Xiaoxi Han, and Bo Zhu. On the Security of Two Threshold Signature Schemes with Traceable Signers. In: Applied Cryptography and Network Security (ACNS'03), LNCS 2846, pp. 111-122. Springer-Verlag, 2003.

[17] S. Xu and R. Sandhu. Two Efficient and Provably Secure Schemes for Server-Assisted Threshold Signatures In: CT-RSA 2003, LNCS 2612, p. 355-372. Springer-Verlag, 2003.