New Collective Signatures Based on the Elliptic Curve 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:There have been many digital signature schemes were developed based on the discrete logarithm problem on a finite field.In this study,we use the elliptic curve discrete logarithm problem to build new collective signature schemes.The cryptosystem on elliptic curve allows to generate digital signatures with the same level of security as other cryptosystems but with smaller keys.To extend practical applicability and enhance the security level of the group signature protocols,we propose two new types of collective digital signature schemes based on the discrete logarithm problem on the elliptic curve:i) the collective digital signature scheme shared by several signing groups and ii)the collective digital signature scheme shared by several signing groups and several individual signers.These two new types of collective signatures have combined the advantages of group digital signatures and collective digital signatures.These signatures have a fixed size and do not depend on the number of members participating in the creation of the final collective signature.One of the advantages of the proposed collective signature protocols is that they can be deployed on top of the available public key infrastructures.

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

1 Introduction

One of the important applications of asymmetric cryptosystems is digital signatures (DS).Authenticatic systems based on digital signatures are quite popular today.Digital signature protocols are developed based on difficult problems in mathematics such as the factorization problem of a large integer,the discrete logarithmic problem on finite field,the discrete logarithmic problem on the elliptic curve,or the problem of finding the roots modulo large primes (a new hard problem).To meet the authentic requirements of many different practical applications,many types of different digital signature schemes have been researched and published:Single (individual) digital signature schemes[1];Blind digital signature schemes[2,3];Group digital signature schemes[4-6].Collective digital signature schemes[3].

In practice there are documents that need i)to be signed by several different signing groups;ii)to be signed by a number of different signing groups and a number of different individual signers.We rely on the advantages of the collective digital signature and the advantages of the group digital signature to build signatures for these cases.This is still a single digital signature but signed by i)all the given signing groups;ii)all the given signing groups and the individual signers.In this paper,we propose the novel digital signature schemes that help to generate signatures for the two cases just mentioned.

The discrete logarithm problem on the elliptic curve has been standardized in the standard ECDSA[7,8]and the standard GOST R34.10-2001[9].We use both standards to build the proposed collective signature schemes.

We use a combination of the collective signature generation technique[10]and the group signature generation technique[6]in building the new collective signature schemes.In these schemes,the public key of signers is masked.This is similar to the blind signature protocols described in[6].

2 Related Basis Collective Digital Signature Schemes

The digital signature protocol on the elliptic curve be described in detail at[11].We based on this protocol to propose protocols of collective digital signature of a signing collective.There are two schemes built here,one based on ECDSA standard and one based on GOST R34.10-2001 standard.These schemes are used to build the collective signature schemes for signing groups and for individual signers.

2.1 Constructing the Collective Signature Scheme Based on the Standard ECDSA

2.2 Constructing the Collective Signature Scheme Based on the Standard GOST R34.10-2001

Russian signature standard GOST R34.10-2001 specifies the DS algorithm based on the elliptic curve (EC) defined over the finite fieldGF(p)with the equationy2=x3+ax+b mod p,wherea,b∈GF(p)andxandyare coordinates of the points on the elliptic curve.

Given an elliptic curve satisfying the requirements of the standard GOST R34.10-2001.Let the pointGon this EC.Ghas the large prime orderq.There are n members in the signing collective.Each of signers selects a private keykj.His/her public key isQj:Qj=kjG,j∈[1,n].The collective signature scheme using the standard GOST R34.10-2001 includes the following procedures:

Thus,the correctness of this protocol has been proved.

3 The Proposed Group Digital Signature Schemes

In this section,we rely on the ECDSA standard[8]and the GOST standard R34.10-2001 to propose two new types of digital signature schemes for a group of signers.We are based on these basis schemes to construct the new collective signature schemes.

3.1 The Group Digital Signature Scheme Based on the Standard ECDSA

3.2 The Group Digital Signature Scheme Based on the Standard GOST R34.10-2001

Thus,the correctness of the protocol has been proved.

3.3 Security Advantages of the Proposed Group Digital Signature Schemes

The group signature schemes proposed in Sections 3.1 and 3.2 have the following security advantages:

• According to formulas(16)and(17)or formulas(28)and(29):The masking coefficientsλiand U are generated by the group manager.λicontains the group manager’s private key.U contains the information of the public key of all members of the signing group who participated in the generation of the last group digital signature.Thus,only the group manager can know who participated in the signature creation because only he/she can open the signature.Since only he/she can calculate the masking coefficientsλiand then calculate U.

• Eqs.(23)and(25)or Eqs.(35)and(36)show that the shared signaturesiof all members of the signing group is checked by the group manager.Only if all is valid,the manager conducts to create the third partsof the group signature which contains his/her shared signature.Thus,if the member’s shared signature is forged,it is also difficult to pass the test expression (23) or(35).

• Another security advantage of the proposed schemes is the use of random parameterρin the process of generating shared signatures of each group member.ρis treated as the second private key.This private key can only be used once,so the secrecy is very high.This also means that,if someone wants to forge a shared signature of a group member,to pass a checking expression(26)or(35),one must solve 2 discrete logarithmic problems to findkandρ(see formula(23)or(35)).

4 The Proposed Collective Digital Signature Schemes

The new collective signature schemes proposed in this section are built based on a combination of the collective digital signature schemes described in Sections 2.1 and 2.2 and the group digital signature schemes described in Sections 3.1 and 3.2.These collective digital signatures are formed in 2 steps:The first step,form the pre-signature;The second step,form the collective digital signature for signing groups.In Section 4.1,we use the signature standard ECDSA to construct the signature for a number of signing groups.Meanwhile,in Section 4.2,we rely on the signature standard GOST R34.10-2001 to construct the signature for a number of signing groups and a number of individual signers.

4.1 Collective Digital Signature Scheme for a Number of Signing Groups Using the Standard ECDSA

Letgsigning groups.There aremactive members in each signing group.Let the public key ofj-th signing group isLj=zjG,wherezjis private key of thej-th group manager(j= 1,2,...,g).These signing groups want to sign on the document M.A set of members in the j-th signing group is denoted bymj.The collective digital signature scheme for several signing groups includes following procedures:

•The signature generation procedure on the document M

4.2 Collective Digital Signature Scheme for a Number of Signing Groups and a Number of Individual Signers Using the Standard GOST R34.10-2001

4.3 Performance Evaluation of the Proposed Collective Digital Signature Schemes

Remember,the individual signer identification procedure needs the participation of the group manager of the signing groups who participated in the formation of the final collective signature.Thus,the computational complexity of this procedure is quite high.This will increase significantly as the number of signing groups,the number of individual signers increases.

We consider the performance of proposed schemes by comparing the time for the signature generation proceduce and the time for signature verification procedure of our schemes and the scheme in[12].Both are collective signature schemes for signing groups,both are built on the difficult problem of the discrete logarithm problem,but the scheme in[12]is in the finite field(in Section 2),the scheme in this paper is in the EC combined with ECDSA standard(in Section 4.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[13]:Th≈Tm,Ts≈29Tm,Tinv≈240Tm,Te≈240Tm.

Suppose there areggroups of signings and eachjthgroup hasmjsigners.The time cost for generating signature components of the proposed digital signature scheme and the collective digital signature scheme in[12]is given in Tab.1.

Table 1:Time cost of the signature scheme in[12]and the proposed signature scheme

Tab.1 shows that the time cost for the generation of signature components and for the signature verification of the proposed collective signature scheme is much lower than that of the similar signature scheme in[12].This disparity will be large as the number of members that participate in signature formation increases when comparing the time cost for constructing the CDSs for several signing groups and several individual signers of the schemes in[12](at Section 3) and the scheme in this paper(at Section 4.2).

5 Discussion

The protocols described in Section 4 represent a new extension of the collective signature scheme[9]proposed for generating a common signature that is shared by an arbitrary group of individual signers and has a fixed size.The uniqueness consists in many signing groups or several signing groups and several individual signers sharing a fixed-size single signature.That combination between the collective signature schemes[9]and the group signature schemes[6,14]is possible because the last schemes use the formation of the collective signature as a preliminary stage of the group signature formation.Analogous combining of the collective signature scheme with the group signature protocols of other types,for example,described in[15-17]appears to be impossible.

In the proposed protocols like the protocols in[10],the private keys used by each signer participating in the process of computing the collective signature is known only for the owner of the respective public key and the security justification of the security can be performed as reducing to the security of the individual signature protocol or to the group signature protocol,directly in line with security analysis provided by[9].

An important advantage of the proposed protocols relates to the possibility of using the existing public key infrastructure for their practical use.Besides,some official signature standards,for example[18-20],can be used as their base cryptoscheme.

6 Conclusion

Thus we have studied and proposed different types of signature schemes using the elliptic curves:i)the collective digital signature scheme for several signing groups(using ECDSA);ii)the collective digital signature scheme for a number of signing groups and a number of individual signers (using GOST R34.10-2001).For each one,we designed the signature generation procedures,the signature verification procedures,prove their correctness.The security advantages and the performance of the novel collective digital schemes were also presented.

With the novelty that the group of authors presented in this article hopes to have practical applications in practice.In the future,we will study and develop collective signature schemes as proposed in this paper,but it only consists of 2 components E and S,like the signatures in[1-4,6,15]by using the EC.

The computational difficulty of the described collective signature protocols is aboutmtimes higher than the difficulty of the group signature protocols[6,12].However the shared signatures of the signing groups can be computed simultaneously,therefore in the case of the parallel computation,their performance is comparable with performance with their base group signature scheme.In the future,we will also study to construct new collective signature protocols under this approach.

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

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