International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 1

ISSN 2229-5518

A Modified (t, n) Threshold Group Signature Generation and (k, m) Threshold Group Signature Verification Scheme

Ganesh Mante,Prof.Dr.S.D.Joshi

Abstract--Globalization of the Internet has boosted electronic information exchange on both the personal and business levels. There is a need of the authentication of messages sent by a group of individuals to another group. A (t, n) threshold group signature scheme is a method for allowing a member of a group to anonymously sign a message on behalf of the group. The idea of threshold cryptography is to protect information by distributing it among a cooperating member. Following some ideas of the classical threshold signature scheme, a (t, n) threshold group signature scheme and (k, m) threshold group signature verification scheme based on discrete logarithm problem is proposed. The group signature is generated by at least t group members and is verified by at least k members in the group. Only one group public key is required. Each group member separately signs the message. The scheme is highly secure and resists the conspiracy attack.

Index Terms-Discrete logarithm, Group Signature, Galois Field, Polynomial, Signers, Threshold, Verifiers

—————————— • ——————————

1. INTRODUCTION

raditionally to authorize the transactions done by corporation by the single person or group of persons is designed and implemented by software control defense mechanism. But considering the security threats in the highly popularized internet and mobile world above schemes are not satisfactory. Many cryptographic techniques are used to solve this problem. If the secret is kept with the single entity, it may cause the malicious damage to the system and there may also be the problem of availability. To overcome such problem the concept of threshold cryptography can be used in which the secret is distributed. Secret sharing refers to method for distributing a secret amongst a group of participants, each of which is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use. There are
three main objects while designing a secure application:

Confidentiality: This can also be called privacy or secrecy and refers to the protection of information from unauthorized disclosure. Usually achieved either by restricting access to the information or by encrypting the information so that it is not

————————————————

Ganesh Mante is pursuing MTech in Computer Engineering inBharati Vidyapeeth Deemed University College of EngineeringPuneMS, India, . E-mail:gmante10@gmail.com

Dr.S.D.Joshi is Professor in Computer EngineeringDepartment inBharati

Vidyapeeth Deemed University College of EngineeringPuneMS, India, . E-mail:sdj@live.in
meaningful to unauthorized individuals or entities.

Integrity: Assuring the receiver that the received message has not been altered in any way from the original. This can be thought of as accuracy. This refers to the ability to protect information, data, or transmissions from unauthorized, uncontrolled, or accidental alterations. The term integrity can also be used in reference to the functioning of a network, system, or application. Integrity is lost if unauthorized changes are made to the data by either intentional or accidental acts. To prevent the loss of integrity from happening, only authorized users should be allowed to modify data.

Authentication: Authentication serves as proof that you are who you say you are or what you claim to be. Authentication is critical if there is to be any trust between parties. Authentication is required when communicating over a network or logging onto a network. When communicating over a network you should ask yourself two questions: 1) with whom am I communicating? And 2) why do I believe this person or entity is who he, she, or it claims to be?

Nonrepudiation: The ability to prevent individuals or entities from denying that information, data, or files were sent or received or that information or files were accessed or altered, when in fact they were.

2. LITERATURE SURVEY

Threshold Cryptosystems has gradually been attractive since the proposal of the first threshold cryptosystem by Desmedt and Frankel in 1989.Numerous international studies had published research results and considerable researches were
devoted to the threshold cryptography. Threshold signature

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 2

ISSN 2229-5518

cryptosystem is an important aspect of threshold cryptography, and represents almost the core of threshold cryptography research.
Li, Hwang and Lee [8] proposed the RSA based threshold signature scheme. In related research [8], it was pointed out that t+1 or t sub secret shareholders can conspire to obtain the system secret, and a conspiracy attack from the participants enables the conspirators to easily generate a group signature. The paper presents a technique where k out of l individuals is required to generate a signature for a message. This is clearly better than having each of the k individuals create k signatures which would cause an increase in bandwidth overhead. The receiver would also be required to perform more calculations and store a large key directory. No interactions between shareholders is necessary for the generation of signature and the secret key is not revealed to any individual even after signatures have been created .The scheme is based on RSA and interpolation polynomials. The scheme fails to withstand the conspiracy attack.
L.Harn [7] proposed a group oriented threshold signature scheme based on Elgamal System. In this scheme any t out of n users in a group can represent this group to sign the group signature. The size of the group signature and the verification time of the group signature are equivalent to that of an individual digital signature. The signature verification process is simplified because there is only one group public key required, the group signature can be verified by any outsider. In addition the scheme proposed does not require assistance of a mutually trusted party. Each member selects its own secret key and the group public key is determined by all group members. Each group member signs a message separately and sends the individual signature to a designated clerk. The clerk validates each individual signature into a group signature.
Li, Hwang and Lee [6] proposed two (t, n) threshold signature methods for resisting the conspiracy attack. One method required a trusted distribution center, while the other did not. These two methods resisted the conspiracy attack by attaching a random number to the sub-keys of all participants, such that the signatures could be protected against tracing from the sub-key. However these schemes failed to resist forgery attack from the internal participants.
Wang, Lin and Chang proposed two new (t, n) threshold signature methods [5].The proposed methods enabled the signers traceable but do not require the attachment of random numbers to sub-keys. The scheme can withstand conspiracy attacks without attaching a secret number. The group’s public key is determined by all members, each member signs a message independently and transmits the individual signature
to a designated clerk who checks and integrates them into a
group signature. A verifier can authenticate the group signature and track back to find the signers.
Tsen, Jan and Chien [4] forged an attack to demonstrate the insecurity in the methods by Wang [5].They summarized the concepts of the attack and created a new threshold signature system that withstands conspiracy attacks [4].The system is a signer-untraceable method against conspiracy attacks, where required two sets of keys, one depended on the discrete logarithm problem and the other on the dissolution of the large integer problem. Both of which attempted to prevent the system participants from conspiring to obtain the system signature key. In reality, the method disabled to prevent the sub-key holders from conspiring to obtain system secrets, and it thus failed to resist conspiracy attack.
Related to the research of threshold signature cryptosystem, the method of [4] by Jan is briefly described in [3].Besides the attack the way to improve the scheme is examined. Later on many threshold group signature schemes with and without trusted party [1] have been proposed. But many of them face the problems of conspiracy attack or insider forgery attack.
Based on the study of above research an attempt to implement the threshold group signature library is proposed [2].In this paper [2] we have modified the scheme at group signature generation and verification protocol. The scheme [2] is modified by using Shamir’s secret sharing scheme for distributing the hash code among m members. When k or more members among m members comes together we can reconstruct the hash code. Using this hash code the group signature is verified. We are not considering the network delay so the algorithms can be executed on single machine. The scheme consists of (t, n) signing and (k, m) verifying. Till now any outsider could verify the group signature. Here in this scheme any m out of k can verify the message. If less then t and less than k members tries to sign and verify the signature signing and verifying is rejected. It can not only satisfy the properties of threshold group signatures, but also withstand the conspiracy attack. The scheme consists of six protocols:

– KeyGen: the group manager uses KeyGen protocol to generate system parameters and his master key.

– Join: a member runs join protocol, together with the group manager, to obtain a certificate as its group membership.

– Sign: a group member anonymously sign a message following sign protocol.

– Verify: a verifier uses verity protocol to check whether a signature is originated from a member in the group.

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 3

ISSN 2229-5518

– Open: the group manager uses open protocol to find the original signer of a signature.

– Revoke: the group manager uses revoke protocol to exclude

3.3 Key Generation Phase II

When all participants complete the Key Generation Phase I
step every Usi computes his Private Key X = (d +

j=1n(fu mod p)mod p,Public key Y=gX mod p, the group

a group member.

public key YU = (Tn

n

i=l

n

ga,O )mod p and additional data

Yd mod p and DS N = Ti=l D-l

mod pwhere D-l

is the

3. PROPOSED THRESHOLD GROUP

SIGNATURE SCHEME

Let p and q be two prime numbers satisfyingq|(p - 1), and let

g = h(p-l)/q mod p , satisfying g > 1 , where0 < h <

p.Suppose Us = {Usl , Us2 ,… Usn } is a set of n signers

Uv = {Uvl , Uv2 ,… Uvm } is a set of m verifiers, and GM is a

trusted group manager. In this scheme, GM acts to authenticate
every participant’s identity, including members in Us and members inUv . All n members in Us share a group of secure
reverse of D in GF(p). Usi then broadcasts his public key Y
.With the same procedure as above, according to the given

threshold k , all m verifiers in Uv could negotiate their own keys. Every Uvi (i = 1,2…, m) gets his own private key , public key Y and their group public key YU .

3.4 Join

When all members in a group have negotiated their communication keys, they can subscribe their public keys and
identity information to GM for register. After communication
parameters of p, q, g.Similarly all m members in Uv share a
group of secure parameters of p, q, g.Let usi and uvj are the
keys have been negotiated every Us

= {Usl

, Us2

,… Usn

} sends

public identities of signers and verifiers. The parameters p, q, g
of both groups are different.

(i, usi, D, Y) to GM to register via a secure channel. After GM

has authenticated his identity, GM adds his public information
into public key status list ofUs . The structure of public key

3.1 Group Formation

This module is used to form the groups of either signer or
verifier. The secure parameters p, q, g are generated after
specifying the number of signers and threshold value .The
public identities usi and uvj of every user is created and
broadcasted for further computations. The parameters are
generated by the head or authorized members of the group.
And the parameters p, q, g of both the signers group and
verifiers group are known to each other.

3.2 Key Generation Phase I

All members in Us negotiate their communication keys as
below:
According to the given threshold valuet, every member of signer group secretly constructs a t - 1 rank polynomial:

fsi (x) = fsi ,O + fsi ,lx + · + fsi,t-l x t-1 mod q

status list for Us is as below:
Table 1: Public Key Status List of Signers Group

Similarly, when all verifiers in Uv have negotiated their own keys, every Uv = {Uvl , Uv2 ,… Uvm } sends (i, uvi, D, Y) to GM

to register via a secure channel. After GM authenticates his
identity, GM adds his public information into public key status
list ofUv. The structure of public key status list for Uv is as
below:

where x is a randomly generated integer in range of q and fsi,t-l 0.Simultaneously, he randomly selects a secret nonzero integer d in GF(p) .Then he computes D = gd mod p and

ga mod p where a = fsi l mod p, (l = 0,1, . . t - 1) . Then U

Table 2: Public Key Status List of Verifiers Group

, si

computes f(u) where f(u) = fsi (usj ) and sends it toUsj (j =

1,2, … n). Every member computes f(u) by putting public

identity of other members in their polynomial .At last Usi
broadcasts D and ga in the set of Us . When every member
receivesf(u), they can verify its validity via the equation

t-l

3.5 Individual Signature Generation

Among the n members in Us , any t participants could sign a

ga mod p = (g

l=O

fsi ,l ) usj mod p

message M on behalf of the group Us .Every

Us = {Usl , Us2 ,… Usn }could generate his own individual

signature as below:
If the equation is true, then f(u) is valid, otherwise invalid.

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 4

ISSN 2229-5518

Firstly, Usi randomly selects a secret integer w from[1, q - 1], and then he computes and broadcasts W = gw mod p and

z = gwd ~ mod p where d isUsi ’s secret random integer

be accepted as valid information. Then using LaGrange’s
interpolation he calculates the M' .

k k

brought during the key generation and d~ is d ’s reverse in

GF(p).After every Usi have received other participants’

M' = f(Wvi) Wvj/(Wvj - Wvi)

information through broadcast, he opens the document to be signed ,get the hash code of document and computes

i=l

j=l,j=ti

r = 'Lt

n

z mod pand s = Xah(M) - rwd ~ mod q , where h

usj

a = Tj=l,j=ti usj-usi .At last Usi sends (usi, r, si) as his own

individual signature on the message M, to the appointed group
signature generator, for example,Usl.

3.6 Group Signature Generation

After the appointed group signature generator, Usi , have received the individual signature (usi, r, si) of Us =

{Usl , Us2 ,… Usn } he firstly verifyUsi ’s identity according to the

public key status list of US .Then he verifies the received
signature of members using the equation

D s mod p W r mod p = ((Yd mod p) (h(M)a)mod q )mod p).

If the equation is true, Usi ’s individual signature is valid,
otherwise invalid. After the appointed group signature
generator have received t valid individual signatures

(r, si)(i = 1,2,.. t) he computes

group signature M: {YU , , r, s, DSA,DSN } could be accepted as a

valid group signature on the messageM. After the group
signature has been accepted as a valid group signature.

3.8 Open

According to the attachment information (s1, s2,… st, us1)of a group signature on the messageM: {YU, , r, s, DSA,DSN }, GM could find the group signature generator Uvl .And then Uvl could find the t original signers according to the attachment

information if necessary. And so every signer of a group can
not cheat others successfully.

3.9 Revoke

To revoke one member from a group, the group manager modifies the end time of the member in public key status list and broadcasts the current public key status list. From then on

t

j=l,j=ti

Yi ai and s = 'Lt

s mod q .

the member could not participate in the group signing phase,
but the former signature he has signed is still valid. The group
The group signature generator randomly selects a secret
integer w from [1, q - 1] where q is parameter of verifier
group and computes:

B = gw mop p , Wvi = D-w mop p , Rvi = gY**w mod p (i =

1,2, . . m) .Instead of sending the plain message the group

signature generator generates a k - 1 rank polynomial:

f(Wvi) = M' + c1 x + · + cn x k-1 mod q

and send f(Wvi) to all the m verifiers. The first constant of the
polynomial contains the hash code. We have used here the
Shamir’s secret sharing scheme..At last he broadcasts the

computing value (B, (Wvi, Rvi)(i = 1,2, … m)) the attachment information (s1, s2,… st, us1) and the group signature on the message M: {YU , , r, s, DSA,DSN }.

3.7 Group Signature Verification

Among the m members in Uv, any k participants could verify
a group signature on a message M on behalf of the group Uv.

Suppose that the k verifying participants are Uvl , Uv2,…..Uvk .

Firstly, with his own private key, every Uvl, Uv2,….. Uvk

computes Evi = BX mod p and submits (uvi, Evi, f(Wvi))to

the appointed group signature verifier, for exampleUvl.When
the appointed group signature verifier, Uvl have received all

(uvi, Evi, f(Wvi)) from k members he firstly verify Uvi ’s

identity.He verifies their Signatures using gEvi mod p =

Rvi mod p. And only when the equation is true, the Evi could

needs to be reestablish again otherwise the group signature cannot be validated.

4. NUMERICAL ILLUSTRATIONS

Let us consider (4,10) threshold group signature scheme and
(3,7) threshold group signature verification scheme. Signers Group (4,10)
p=1816218345 q=908109173 g=49348095 n=10 t=4
Table 1: t-1 Rank Polynomial for Signers Group

Table 2: Secret and Public Data or Signers Group

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 5

ISSN 2229-5518

Table 5: Individual Signature of t members
DsN=1764011415 DsA=1510672311 Yu=1688776651 s=39246999 r=1083719607
Group Signature=149868269, 1083719607, 39246999,
1041624746, 1616950608,694491120
Hash Code h (M) =259990256
Table 3: Private and Public Keys for Signers Group
Verifiers Group (3, 7)
p=1233440437 q=313860109 g=750023093 t=7 n=3
W=280422927 B=500777311 Yu=540651610
Table 6: t-1 Rank Polynomial for Verifiers Group
Table 4: Individual Signature generation parameters

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 6

ISSN 2229-5518

6 89749836 218576337 + 50240072x +
81571354x^2
1. In key generation Phase I the members cannot send false

f(u) to other members within the group. This can be verified

using the equation
Table 7: Secret and Public Data for Verifiers Group

t-l

ga mod p = (g

l=O

fsi ,l ) usj mod p

Table 8: Private and Public Keys for Verifiers Group

Table 9: Parameters for group signature verification

5. SECURITY ANALYSIS

The security of the proposed scheme is based on the difficulty to solve the discrete logarithm problem and difficulty to break
Shamir’s secret sharing scheme.
2. In threshold group signature generation the individual
member cannot send false signature (usi, r, si) to the group
signature generator. This can be verified using the equation

D s mod p W r mod p = ((Yd mod p) (h(M)a)mod q )mod p)

3. If t - 1 or less signers try to sign the message the group
signature cannot be generated.
4. If k - 1 or less verifiers try to verify the message the group signature cannot be verified.

6. COCLUSION

The security of the proposed scheme is based on the difficulty to solve the discrete logarithm problem and difficulty to break Shamir’s secret sharing scheme which we have used in threshold group signature generation and verification. Instead of sending the plain message with group signature we have encrypted the message using AES which maintains the integrity property. We have taken the double hash code of message to be signed so there are no limitations for message size. When k or more members come together the hash code can be reconstructed using Lagrange’s interpolation and then only the threshold group signature can be verified. We have introduced a scheme where at least t of n signers could cooperate to create a valid group signature on behalf of the group of signers. Similarly at least k of m verifiers could cooperate to verify a group signature on behalf of the group of verifiers.

ACKNOWLEDGEMENT

I wish to thank all the people who gave me an unending support right from the stage the idea was conceived. I am also grateful to BVDU team for providing us with the setup for work, without which implementation was just impossible. I express my profound thanks to Prof.Dr.S.D.Joshi and Dr.S.H.Patil,Head of Department, Dr.Anand Bhalerao,Principal
,BVDU College of Engineering,Pune who have guided and
helped me in preparation of this paper .

REFERENCES

IJSER © 2011

http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 2, Issue 7, July-2011 7

ISSN 2229-5518

[1] J.V.Merve, D.S.Dawoud and S.McDonald,”A fully Distributed Proactively Secure Threshold –MultiSignature Scheme”, IEEE Transactions on Parallel and Distributed Systems, Vol.18,No.4 ,2007

[2] F.Li,J.Yu and H.Ju, ”A new threshold Group Signature scheme based on discrete logarithm problem”, IEEE Eight ACIS International conference on software engineering, artificial intelligence ,Networking and Parallel Distributed computing ,2007.

[3] Y.F.Chung.C.H.Liu, F.Lai and T.S.Chen, ”Threshold signature scheme resistible for conspiracy attack”, IEEE Proceedings of the Seventh International Conference on Parallel and distributed Computing, Applications and Technologies,2006.

[4] J.Camenisch and A.Lysyanskaya, A signature scheme with efficient protocols, In SCN’02, LNCS 2576, 2002, pp. 268-289.

[5] D.Boneh, X.Boyen, and H.Shacham, Short group signatures, In

Advances in Cryptology-Crypto’04, LNCS 3152, 2004, pp. 41- 55. [6] D.Boneh and H.Shacham, Group signatures with verifier-

local revocation, In Proc. of the 11th ACM Conference on Computer and Communications Security (CCS 2004) , 2004, pp. 168-177.

[7] J.Camenisch and J.Groth, Group signatures: Better efficiency and

new theoretical aspects, In Security in Communication Networks

(SCN 2004), LNCS 3352, 2005, pp. 120-133.

[8] J.K.Jan, Y.M.Tseng,and H.Y.Chien, ”A threshold signature scheme withstanding the conspiracy attack”, Communications of Institute of Information and Computing Machinery,Vol.2,No.3,1999.

[9] C.T.Wang, C.H.Lin and C.C.Chang, ”Threshold signature scheme s with traceable signers in group communications”, Elsevier ,Computer Communications,Vol 21 ,No.8,1998.

[10] C.M.Li, T.Hwang and N.Y.Lee,”Threshold multisignature schemes where suspected forgery implies traceability of adversarial shareholders”, Advances in Cryptology-Proceedings of EUROCRYPT ’94, LNCS, Vol.950, Springer –Verlag, 1995.

[11] L.Harn,”Group-oriented (t,n) threshold digital signature scheme and digital Multisignature”, IEEE Proceedings-Computers and Digital Techniques, Vol.141, No.5, 1994.

IJSER © 2011

http://www.ijser.org