New Representative Collective Signatures Based on the Discrete Logarithm Problem

Tuan Nguyen Kim,Duy Ho Ngoc and Nikolay A.Moldovyan

1School of Computer Science,Duy Tan University,Da Nang,Vietnam

2Department of Information Technology,Ha Noi,Vietnam

3ITMO University,St.Petersburg,Russia

Abstract:The representative collective digital signature scheme allows the creation of a unique collective signature on document M that represents an entire signing community consisting of many individual signers and many different signing groups,each signing group is represented by a group leader.On document M,a collective signature can be created using the representative digital signature scheme that represents an entire community consisting of individual signers and signing groups,each of which is represented by a group leader.The characteristic of this type of letter is that it consists of three elements (U,E,S),one of which (U) is used to store the information of all the signers who participated in the formation of the collective signature on document M.While storing this information is necessary to identify the signer and resolve disputes later,it greatly increases the size of signatures.This is considered a limitation of the collective signature representing 3 elements.In this paper,we propose and build a new type of collective signature,a collective signature representing 2 elements (E,S).In this case,the signature has been reduced in size,but it contains all the information needed to identify the signer and resolve disputes if necessary.To construct the approved group signature scheme,which is the basic scheme for the proposed representative collective signature schemes,we use the discrete logarithm problem on the prime finite field.At the end of this paper,we present the security analysis of the AGDS scheme and a performance evaluation of the proposed collective signature schemes.

Keywords:Elliptic curve;signing group;individual signer;collective signature;group signature

1 Introduction

To ensure the security of transactions on the network,people often use authentication systems based on digital signatures.Digital signatures[1]not only help authenticate the origin of information,but also help check the integrity of information as it is transmitted from source to destination.In addition,digital signatures also help prevent the repudiation of a communication partner.

In order to meet many different authentication requirements in practice,many types of digital signature schemes have been researched and published such as single digital signature scheme[2],multiple digital signature scheme[3],blind digital signature scheme[4,5],group digital signature scheme[6-9],collective signature scheme[10],blind collective digital signature scheme[11],representative collective signature scheme[12].

It is known that a group signature is a multi-signature formed by a group of signers under the control of the group leader (who manages the signing group).This type of signature usually consist of two components,or pairs of two sufficiently large integers (E and S).A group signature scheme must meet the following minimum requirements:i) A set (subnet) of any individual signers the individual,selected from a group of members,can generate a signature,representing the signing group,on document M;ii)The signing group manager can identify everyone who participated in the group signature formation process of the signing group they manage,and only the group manager can do this;and iii)Persons outside of the signing group cannot establish a subset of individual signers so that these people create group signatures representing the signing group.

The Approved Group Digital Signatures (AGDS) type proposed by us[13],to serve as the basic scheme for the representative collective signature scheme,also satisfies the following additional conditions:i)No anyone in the signing group,including the group manager,knows the private key used by the individual signers in the group signature formation process;ii)Group signatures are formed in two stages:First,each individual signer generates the associated parameters and their shared personal signature and then passes it all on to the group manager.The group manager then checks the validity of each signature received by the shared individuals,if all are valid then the manager proceeds to generate the final group signature,from the shared signatures and signature of the administrator himself.This is why this signature is called a consent group signature.

Therefore,to meet the above conditions,the approved group signature has been designed in the form of a set of three components U,E,and S[10].The U component is used to store information of all participating members participating in the formation of group signatures,as the basis for the identification of the signer later.Obviously,it is necessary to save the information of those who participated in the formation of the group signature,but it makes the size of the group signature significantly increase,which is considered a limitation of this group signature scheme.Because the representative collective signature scheme is built on the basis of the AGDS scheme,this is also a limitation of the three-component representative collective signature(U,E,S).

To overcome this limitation,we change the AGDS schema,and subsequently change the representative collective signature scheme,so that it allows the creation of group signatures and representative collective signatures consisting of only sets of 2 components (E,S)[13].Of course,it still contains all the necessary information so that it can later be identified who participated in the creation of the signing group’s group signature.This information is contained in the random component(R),which is used to form the E component of the group signature,the ultimate representative collective signature.

In three-element grouping signature schemes[13],the random parameter (R) is formed from a randomly chosen numeric value (t).In a 2-component grouping signature protocol,since the information of all the signers involved in the signature generation process is embedded in the random parameter (R),the random value (T) is not chosen in the random way that it is generated by some pseudo-random value generator algorithm.The random parameter in this case not only satisfies the requirements of uniqueness,secrecy,and unpredictability but also ensures the function of protecting the private keys of the participants in the group signature generation process of the signing group.The pseudo-random number generation algorithm used in the group signature schemes below fulfills this.

The AGDS generation procedure in this case,which generates a 2-component group signature,is performed through the following steps:

1.The set of individual signers together create a collective signature on the document M to be signed.Then,send the newly created collective signature(Ecol,Scol)to the group manager.

2.The group manager uses the received collective signature (Ecol,Scol),document M,and his private key z to compute a pseudo-random value T,according to a predefined algorithm.

3.Using the calculated pseudo-random value,the group manager computes the random component of the group signature(R),and then computes the two components of the team leader’s signature(E,S)on document M This is also the group signature of the whole group signing on document M.

Thus,we reduce the size of the group signature and the representative collective signature[10]by not using the U element to contain the signer information,but embedding this information in the random parameter R.That is the group signature and the representative collective signature are reduced to two elements(E,S),but still contain all the necessary information to serve the identification of the signer later.

In this paper,we use the difficult problem of the discrete logarithm on prime finite fields to build both forms of collective signature schema representing 2 components:i)Collective signature shared by multiple signing groups and ii)Collective signatures shared by multiple signing groups and many individual signers.The collective signature scheme and the consent group signature scheme are used as the basis for the proposed collective signature scheme.

2 Related Basis Digital Signature Schemes

2.1 The Collective Signature Scheme Based on the Discrete Logarithm Problem(The CDS-2.1 Scheme)

2.2 The Approved Group Signature Scheme Based on the Discrete Logarithm Problem(The GDS-2.2 Scheme)

This section describes the two-component approved group signature scheme.The signing group in this case consists of m signers and one who plays the role of group manager.The input parameters are selected as shown in the CDS-2.1 scheme.M is the document that needs to have a group signature on it.

Each signer generates a random secret number to serve as the private key.The public keyyjis calculated by the formula:yj=αxj mod p;j=1,2,3,...,m;The group manager(GM)also chooses a random secret numberz,z ＜q,as the private key.GM’s public key is:Y=αz mod p.This Y is also the public key of the signing group.

The main procedures of the two-component approved group signature scheme on the document M are described below.

?The procedure for generating the approved group digital signature on the document M

The group signature in this case is formed through two stages:

i) Creating a collective signature on documentM,made by a collective ofmindividual signers;

ii) On the basis of the collective signature that has just been created,the group manager creates a group signature of 2 components,representing the whole signing group

1.Individual signers create a collective signature on the documentM:

1.1.Eachisigner generates a random numberti,ti ＜r,and then computesRi:

Then sendRito the other signers in the signing group(i=1,2,...,m).

1.2.Any signer in the group,or all,calculateRcol:

And calculateEcol:

where:FHis a given hash function,the value ofEcolis the first element in the collective signature.

1.3.Eachisigner calculate the personal share valueSi:

Then,sendsSito other signers in the signing group.

1.4.Any signer in the signing group,or all,calculateScol:

So the tuple(Ecol,Scol)is the collective signature of a signing group of m members.The length of the signature is:|Ecol|+|Scol|≈240 bit.

This collective signature is forwarded to the group manager,

2.The group manager checks the validity of the received collective signature (Ecol,Scol) by checking the precision of the following expression:

where:

If the collective signature is valid,the group manager will calculate the pseudo-random value T:

where:Hz=FH(M,z)mod qand

3.The group manager calculates the values R,E and S as follows:

Thus,the tuple (E,S) is the two-component approved group signature of the signing group including m signers and the group manager on the document M.

?The procedures for verification the approved group digital signature on the document M

To check the validity of the approved group signature received with the document M,the verifier performs the following steps:

1.Calculate the value of the random parameterR*using the following formula:

2.Calculate the value of component E*using the following formula:

3.Compare E*with E.If E*=E:The received signature is valid;otherwise,it is invalid and will be rejected.

? Proof of the correctness of the GDS-2.2 scheme:

The correctness of this representative collective signature scheme is shown through:i) The existence of a formula to check the shared signatureSjof each signing groupRj;ii)The existence of the collective signature test formulaRcoland iii)The existence of the test expressionE*=E.Detailed as follows:

a) The correctness of the formula to check the shared signature per signer:

It is easy to see that the shared signature checking formula is always correct:

b) The correctness of the formula for checking collective signatures:

It is easy to see that the collective signature checking formula is always correct:

c) The correctness of the group signature checking procedure:

Conspicuously,the signature checking expressionE*=Ealways exists:

R*=Y-E αE-1S mod p

=α-zE αE-1E(T+zE) mod p

=αT mod p=R

And calculates:

E*=FH(M||R*)mod2128

=FH(M||R) mod2128=E

Thus,the expressionE*=Ealways exists:This proves that the correctness of the signature checking procedure,or the correctness of the GDS-2.2 scheme is always guaranteed.

3 Constructing the Proposed Collective Digital Signature Schemes Based on the Discrete Logarithm Problem on Prime Finite Field

3.1 Constructing the Two-Element Collective Digital Signature Scheme for Signing Groups(The RCS.01-3.1 Scheme)

This scheme generates a collective signature for g signing groups,with the public key of each group manager(GM),and the public key of each signing group:mod p;with j=1,2,...,g,and Xjis the secret key of j-th GM.Suppose that the j-th group consists of mjindividual signers.M is a document to be signed on.The protocol of collective signatures for signing groups is descibed as follows:

?The procedure for generating the collective digital signature for g signing groups on the document M:

Including these following steps:

1.Each j-th group generates a group signature according to the GDS-2.2 signing group scheme above and then send Rjto all the remaining groups in the signing pool.

2.A certain GM in the collective,or all,calculates the values of R and E by the following formulas:

E is the first component of the collective signature.

3.GM of each j-th signing group continues to execute:

-Calculate the shared composition Sjof the signing group:

-Send Sjto all other GM in the signing group.

4.A certain GM in the collective,or all,does the final works:

-Verify the precision of the shared component Sjof each signing group by the following formula:

-If all Sjsatisfied the test formula,then the third element S of the collective signature is calculated by the formula:

Thus,the value par(E,S)is the collective digital signature,two components,of a collective of g signing groups on the document M.

? The procedure to verification the collective digital signature for g group signing on the document M:

To check the validity of the signature received with the document M,the verifier performs the following steps:

1.Calculate collective public keyYcolusing the formula:

2.Calculate theR*using the following formula:

3.Calculate theE*using the following formula:

4.Compare E*with E.If E*=E:The received signature is valid;otherwise,it is invalid and will be rejected.

? The proof of the correctness of the RCS.01-3.1 scheme:

The precision of this representative collective signature scheme is shown through:i)The existence of a shared signature verification formula shared by the signing team leaders;and ii)Existence of the test expression in the signature check procedure.

a) Prove the correctness of the member’s signature:

It is easy to see that the shared signature checking formulaSjshared by the signing team leaders always exists:

b) Prove the correctness of the last signature:

Conspicuously,the signature check expressionE*=Ealways exists:

Thus,the expressionE*=Ealways exists:This proves that the correctness of the signature checking procedure scheme is always guaranteed.

From(a)and(b):The correctness of the RCS.01-3.1 scheme is guaranteed.

3.2 Constructing the Two-Element Collective Digital Signature Scheme for Signing Groups and Individual Signers(The RCS.02-3.2 Scheme)

Suppose there is a signing collective consisting ofgsigning groups andmindividual signers,and want to create a representative collective signature on the document M.Assume that thej-thsigning group consists ofmsigning members (mj),these people are designated to participate in the formation of the group signature of thej-thsigning group(j=1,2,...,g),and each individual signer is considered as a one-member signing group.

The input parameters,secret key,public key...are selected and calculated as the scheme RCS.01-3.1.

? The procedure for generating the collective digital signature for g signing groups and m individual signers on the document M

Including these steps:

1a.The GM of each group performs:

- Generate a group signature according to the scheme for the GDS-2.2 signing group above and then sendRjto all GM of the signing groups in the signing collective.

-Rjis the shared component of thej-thsigning group used to generate a random parameter of the collective signature.

1b.Eachj-th:

- Choose a random numbertjand calculate the random valueRjusing the following formula:

- SendRjto all individual signers and other GMs in the signing collective.

2.A GM or an individual signer in the collective calculates the values ofRandEby using the following formula:

where:j=1,2,3,...,g+m.Eis the first element of the signature.

3a.GM of each j-th group will:

- Calculate the shared componentSjof thejgroup by using the following formula:

- SendSjto other GM-s and other individual signers in the signing collective.

3b.Eachj-thindividual signerj (j=g+1,g+2,...,g+m)will:

- Calculate their shared componentSjby the following formula:

- SendSjto other GM-s and other individual signers in the signing collective.

4.A GM or an individual signer in the signing collective will:

- Check the validity of eachSjby using the following formula:

withj=1,2,...,gand

withj=g+1,g+2,...,g+m

- If all the conditions are satisfied,the third component of the group signature will be calculated by the formula:

Thus,the value pair (E,S) is a collective signature,two components,of a collective consisting ofgsigning groups andmindividual signers on the document M.It represents this collective signing.

? The procedure for verification the collective digital signature for multiple signing groups and individual signers on the document M

To check the validity of the signature received with the document M,the verifier performs the following steps:

1.Calculate the collective public key of the signing collective by using the following formula:

2.Calculate the random parameter value by using the following formula:

3.Calculate the E*using the following formula:

4.Compare E*with E.If E*=E:The received signature is valid;otherwise,it is invalid and will be rejected.

? The proof of the correctness of the RCS.02-3.2 scheme

The precision of this representative collective signature scheme is shown through:i)The existence of a formula to check the shared signature Sjof each signing group;ii)The existence of the signature test formula shared Sjby each individual signer and iii)The existence of the test expressionE*=E.

a) The correctness of the formula to check the shared signature of m group managers:

Conspicuously,the formula for checking the shared signature of each group manager always exists:

b) The correctness of the formula to check the shared signature per signer:

Conspicuously,the formula for checking the shared signature of each group manager always exists:

c) The correctness of the procedure for checking the representative collective signature:

Conspicuously,the signature checking expression E=E*always exists.

and calculate:

Thus,the expression E*=E always exisits:This proves that the precision of the signature checking precedure,or the precision of the RCS.02-3.2 scheme is always guaranteed.

From(a),(b)and(c):The correctness of the RCS.02-3.2 scheme is guaranteed.

4 Security Analysis and Performance Evaluation

4.1 Security Advantages of the Proposed Collective Signature Schemes

The approved group signature and the approved group signature scheme has the following security advantages:

? The group signature in this paper is built based on the discrete logarithm problem on the prime finite field,so it inherits all the security advantages of this difficult problem.The same is true for the group approved digital signature scheme.

? Signing group members and the group manager can both use a pair of their private key and public key for both purposes:Forming private signatures and participating in group signature formation.As a result,this scheme can be fully deployed on existing PKI (Public Key Infrastructure)systems[14].

? The signer’s private key and secret keys are not used directly in the group signature formation process,nor are they passed on to the group manager and other members of the signing group.In this case,the security and privacy of the values involved are guaranteed.

? Using the group manager’s public key Y as the public key of the signing group makes it possible both to check the validity of the signature(of the verifier)and to change the set of participants that form the signature(of the group manager)have become much more convenient.

? The random parameterstiis treated as the second secret key of the signing group member.Unlike the first secret key,the private key,tirandomly chosen for each signature generation,i.e.,it is used only once.This results in also a random and unique R component in each group signature generated on document M.The“single-use”here enables the signing collective to generate different signatures across documents are different,although they still use the same original public key and private key pair.Thus,it is difficult for an attacker to use the signature collection method of the signing group on different documents to find out the secret components in the received signature set.

The proposed representative collective signature scheme is built on the basis of the approved group signature scheme,so it fully inherits the advantages of this scheme.

4.2 Performance of the Proposed Collective Signature Schemes

We evaluate the computational performance of the two-element representative collective signature schemes by calculating the time cost that the scheme takes for the signature generation process(Signature generation procedure) and the need for the signature verification process (Signature verification procedure).The time costs of representative collective signature schemes proposed in this paper are shown in Tab.1.

Notations:Th:Time cost of a hash operation inZp;Ts:Time cost of a scalar multiplication inZp;Tinv:Time cost of a inverse operation inZp;Te:Time cost of an exponent operation inZp;Tm:Time cost of a modular multiplication inZp.

According to[15]:Th≈Tm,Ts≈29Tm,Tinv≈240Tm,Te≈240Tm,Tsqrt≈290Tm.

Information from Tab.1 shows that the time cost for signature generation and signature checking of a two-element representative signature scheme is not much reduced compared to a three-element scheme[10],of course,if both Both schemes are built on the same difficult problem and/or the same digital signature standard.The advantage of the new representative collective signature scheme is that it still produces a shorter collective signature,but still ensures the security level and meets the basic requirements of a representative collective signature scheme.

Table 1:Time cost of the proposed collective signature scheme:RCS.01-3.2 and RCS.02-3.3

5 Discussion

The pseudo-random number generation algorithm T[13]that we use is guaranteed to contain all the information of everyone who participated in informing the signature and it is also easy to identify the signer later.Indeed,when it comes to identifying those who have previously participated in the formation of the consent group signature,the group manager only needs to perform the following steps:

- Use the group signature(E,S)to recalculate T by using the following formula:

- Calculate:

- And then recalculate the collective signature value using the formula:

- Select a signing group(subset)consisting of any m members from the signing collective(this is a group of signers selected from the signing collective,they are assigned the task of creating a collective signature on document M):Use public key of this signing group to generate the collective public key.Use the newly computed collective public key to recalculate the Ecol||Scol:If this value is equal to the Ecol||Scolof(44),it is the people in this signing group who participated in the generation of the set signature body of collective sign;Otherwise,the group manager will choose another signing group and do the same until they find a signing group whose public key results in a matching E_col||S_col value pair(44).That is,iterate until the identifier is signed by the signers who have participated in the creation of the collective signature,then stop(Here accepted:The probability of coincidence is negligible).

6 Conclusion

A representative collective signature is a form of signature formed by a group of signatures whose members are drawn from different signing groups and/or are from individuals of the same level with the signatories.It is a requirement of this type of signature that it contains information regarding all signers who participated in the signing process.This information is needed for the identification of the signer and to solve the“repudiation”responsibility issue later.We have proposed and implemented a representative collective signature scheme that only has two components(E,S)while still meeting the requirements for a representative scheme.

In[13],we proposed a approved group signature protocol that entails two components.The advantages of this protocol are i)All signer information is embedded in the collective signature(Ecol,Scol),precisely in the pseudo-random parameter T;ii)The group manager can easily identify all those who participated in the formation of the group’s consent group signature,this is possible thanks to the special structure of the parameter T;and iii)Only the group manager can perform the“opening”of the group signature to identify the signer since only this person knows must know the secret key z,a very important component in T.

In addition to having the same security advantages of the three-component signature scheme and the consensus group signature protocol,the two-component collective signature scheme also exhibits the following capabilities:i)Helps to create signatures of shorter size,equal to|E|+|S|,but keeping the same level of security;ii)Helps to reduce time costs for signature generation and signature checking process.To achieve these advantages,the U component is removed from the signature,with the information of all signers whose signatures were used to form the signature stored in a pseudorandom parameter.

In this paper,we use the discrete logarithm problem on a prime finite field to build the proposed collective signature,hence the signature size and time cost for the signature formation/checking process not significantly reduced.We have reason to believe that,if we use the discrete logarithm problem on the elliptic curve[16,17],combined with the GOST R34.10-2012 signature standard[18,19],to build a collective signature scheme representing two components,signature size,and associated time costs will be greatly reduced.This is our future work.

Funding Statement:We received funding for this research from Duy Tan University,Danang,550000,Vietnam.https://duytan.edu.vn/.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.