IJCNC 07

CONSTRUCTING NEW COLLECTIVE SIGNATURE SCHEMES BASE ON TWO HARD PROBLEMS FACTORING AND DISCRETE LOGARITHM

Tuan Nguyen Kim¹, Nguyen Tran Truong Thien^1,
Duy Ho Ngoc² and Nikolay A. Moldovyan³

¹School of Computer Science – Duy Tan University, Da Nang, Vietnam
²Department of Information Technology, Ha Noi, Vietnam
³SPIIRAS, St. Petersburg, Russia

ABSTRACT

In network security, digital signatures are considered a basic component to developing digital authentication systems. These systems secure Internet transactions such as e-commerce, e-government, ebanking, and so on. Many digital signature schemes have been researched and published for this purpose. In this paper, we propose two new types of collective signature schemes, namely i) the collective signature for several signing groups and ii) the collective signature for several individual signings and several signing groups. And then we used two difficult problems factoring and discrete logarithm to construct these schemes. To create a combination of these two difficult problems we use the prime module p with a special structure: p = 2n +1. Schnorr’s digital signature scheme is used to construct related basic schemes such as the single signature scheme, the collective signature scheme, and the group signature scheme. The proposed collective signature schemes are built from these basic schemes. The proposed signature scheme is easy to deploy on existing PKI systems. It can support PKIs in generating and providing a unique public key, a unique digital signature, and a unique digital certificate for a collective of many members. This is essential for many collective transactions on today’s Internet.

KEYWORDS

Network security, digital signature authentication, collective signature, group signature, signing group.

1.INTRODUCTION

To ensure the security of transactions on the Internet, people often use authentication systems based on digital signatures. A digital signature not only supports “authentication” of the origin of information but also helps to check the “integrity” of information when it is transmitted from source to destination and prevent the “non-repudiation” of a communication partner.

Most of the existing authentication systems are built on the basis of single digital signature schemes, so it can only support the validation of an individual signer, it is difficult to validate for a collective of many signers. In this paper, we propose and build a signature scheme that can support authentication for a group of signers, with different functions, with only a single public key and signature. This new authentication request is described below.

Assume that there is a collective made up of several groups, each of which has a large number of members and is managed by a group leader. There are another few individual members in this collective that do not belong to any groups, but they are functionally equivalent to the group leaders. The problem is how to create a single digital signature [1-2] that represents this collective. The requirement of digital signature-based authentication [3-4] for a multi-functional collective is quite common in today’s cyberspace. Both group signature protocols [5-9] and collective signature [10] ones can be used to produce a unique signature for a group of multiple signers, but they cannot be used to generate a common signature for a multi-level signing collective as described above. The reason for this is that the group signature scheme [11] can only create a common signature for each group, and the collective signature scheme [12] can only generate a common signature for the group leaders and individual members, or for all collective members [12]. Therefore, we propose a new type of multi-signature scheme, the representative collective signature scheme, which is structured from the combination of the group signature scheme and the collective signature scheme.

Two stages are required to create the representative collective signature. Firstly, the group signature protocol is used to establish group signatures for each group of the collective. The collective signature protocol is then used to generate collective signatures from each group and every other individual. The final signature represents a signing collective made up of several signing groups and individual signers, and it comprises the information of everyone who participated in the formation of this signature.

Most of the digital signature schemes can be built based on a difficult problem or at the same time two difficult problems [13-15]. In this article, we utilize Schnorr’s digital signature standard [16] to develop two types of representative collective signature schemes using two tough challenges simultaneously. For the discrete logarithm problem [17-18], we use a specially structured prime modulo, 𝑝 = 2𝑛 + 1, where 𝑛 = 𝑞′𝑞; 𝑞′ and 𝑞 are two large primes of magnitude 512 bits, or 1024 bits, used as the signer’s private key. When attempting to find 𝑞′ and 𝑞 from 𝑛, the factorization problem [19-20] is applied.

2.THE RELATED BASE DIGITAL SIGNATURE SCHEMES

The Schnorr digital signature protocol is built on the difficult problem of the discrete logarithm in prime fields, with the input parameter set selected according to the DSA digital signature standard, but without constraints on size and structure of 𝑝 and 𝑞. We propose a modification from the Schnorr scheme by i) Choosing prime modulus with special structure, 𝑝 = 2𝑛 + 1, where 𝑛 = 𝑞’𝑞; 𝑞’ and 𝑞 are large prime numbers having the 512 bit size or more (the primes 𝑞’ and 𝑞 are such that the value 3 does not divide 𝑞’ − 1 nor 𝑞 − 1); ii) Change the expression for calculating the value S in the the signature generation procedure and iii) Change the expression 𝑅∗ in the signature checking procedure (𝑆 is replaced by the parameter 𝑆􀬶). A new prime modulus has been used for constructing the randomized signature security of which is based on the factorization of the value 𝑛 = (𝑝 − 1)/2.

2.1. The Single Signature Scheme (The SDS-2.1 scheme)

In this scheme we select the parameter 𝛼 having the order 𝑛 𝑚𝑜𝑑𝑢𝑙𝑜 𝑝. The primes 𝑞’ and 𝑞 are
elements of the private key.

We assume that the signer has a secret key 𝑥 (1 < 𝑥 < 𝑛 − 1), 𝑥 is chosen at random. The
private key of the signer is 𝑥. His/Her corresponding public key 𝑦: 𝑦 = a^x mod p.

Let 𝐹_H be a one-way hash function such as SHA-1 or SHA- 2, which produces the hash value 𝐻
from the document 𝑀: 𝐻 = 𝐹_H(𝑀).

The signature scheme based on factoring and discrete logarithm problems is described as below:

• The signature generation procedure on the document M:

It includes the following steps:

1. The signer generates the random value 𝑘, 𝑘 < 𝑛, and then computes the value 𝑅:
   𝑅 =a^x mod p.
2. The signer computes the value E:

where d is a large prime, |d| = 160 bits; and 𝐻 is a hash value of the document 𝑀. The value 𝐸 is the first part of the signature.

3.The signer computes the value 𝑆:

𝑆 = (𝑘 + 𝑥𝐸)^1/2𝑚𝑜𝑑 𝑛 

such that:

𝑅 =𝛼^s2 𝑦 ^-E    𝑚𝑜𝑑 𝑝 

The pair of value (𝐸, 𝑆) is the signer’s signature on the document M.

• The signature verification procedure on the document M:

It includes the following steps:

1.The verifier computes the value 𝑅^∗:

2.The verifier computes the value 𝐸^∗:

𝐸^∗ = 𝑅^∗𝐻 𝑚𝑜𝑑 d,

3.The verifier compares values 𝐸^∗ with 𝐸. If 𝐸^∗ = 𝐸: The signature is valid; Otherwise the signature is invalid. It is rejected

•  Proof of correctness of the SDS-2.1 scheme:

To prove the correctness of this signatue scheme we only need to prove the existence of the equation 𝐸^∗= 𝐸.

               It is easy to see 𝑅^∗ = 𝑅. Indeed:

Since 𝑅^∗ = 𝑅 so 𝐸^∗ = 𝐸 (𝐸^∗ = 𝑅^∗𝐻 𝑚𝑜𝑑 d = 𝑅𝐻 𝑚𝑜𝑑 d = 𝐸) is always exists. The correctness of the SDS.2-1 scheme has been proved.

The collective signature scheme described below (the CDS-2.2 scheme) is built on the basis of this signature scheme (the SDS-2.1 scheme).

•    The Collective Signature Scheme (the CDS-2.2 scheme)

We assume that there are 𝑚 signers in the signing collective, 1 ≤ 𝑖 ≤ 𝑚, to sign the same document 𝑀. Each signer randomly selects an integer 𝑥i from the interval [1, 𝑛 − 1] and computes a corresponding public key: 𝑦i = 𝛼^xi 𝑚𝑜𝑑 𝑝 (𝑥i  is the secret key of the i-th user). The collective signature scheme based on factoring and discrete logarithm problems (CDS-2.2) is described as below:

• The collective signature generation procedure on the document M

It includes the following steps:

1. Each signer selects a random number 𝑘i, 𝑘i ∈ [1, 𝑛 -1], and then computes the value 𝑅i:

𝑅i  = 𝛼^ki  𝑚𝑜𝑑 𝑝

2.The signer sends R_i to all other signers in the signing collective One of the signers in the signing collective, or a element in the PKI system, calculates the common randomization value 𝑅:

Anh calculates the first part of the collective signature:

𝐸 = 𝑅𝐻 𝑚𝑜𝑑 d

where d is a large prime, |d| = 160 bits; and 𝐻 is a hash value of the document 𝑚.

The value 𝐸 is sent to all signers in the signing collective.

3.Each signer computes it’s a shared signature 𝑆i:

𝑆i   =  (𝑘i + 𝑥i𝐸)^1/2𝑚𝑜𝑑 𝑛

4.One of the signers in the signing collective, or a element in the PKI system, calculates the second element of the collective digtal signature 𝑆:

The pair of value (𝐸, 𝑆) is the collective digital signature of the signing collective, there are 𝑚 signers, on the message M.

• The signature verification procedure on the document M

It includes the following steps (the verifier can be a element in the PKI system):

4.The verifier compares values 𝐸^∗ and 𝐸. If 𝐸^∗ = 𝐸: The signature is valid; Otherwise the signature is invalid. It is rejected.

• Proof of correctness of the CDS-2.2 scheme:

To prove the correctness of this signatue scheme we only need to prove the existence of the equation

𝐸^∗ = 𝐸.

It is easy to see 𝑅^∗ = 𝑅. Indeed:

Since 𝑅^∗ = 𝑅 so 𝐸^∗ = 𝐸 (𝐸^∗ = 𝑅^∗𝐻 𝑚𝑜𝑑 d = 𝑅𝐻 𝑚𝑜𝑑 d = 𝐸) is always exists.

The correctness of the signature scheme has been proved.

It is easy to see that, in this scheme, none of the signers generates his/her individual signature. The signer generates only its shared signature in the collective signature that corresponds exactly to the given document M and to the assigned set of m users. Besides, it is computationally difficult to manipulate with shares 𝑆₁, 𝑆₂, … , 𝑆m, and compose another collective digital signature, relating to some different set of users.

3.   THE PROPOSED SIGNATURE SCHEMES

In this part, we first construct a group signature scheme for a signing group of 𝑚 members using the group signature protocol provided in [8]. Then, we utilize this scheme and the collective signature scheme mentioned in section 2.2, as the basic schemes, to build two types of the representative collective signature scheme: i) the collective signature for several signing groups and ii) the collective signature for several individual signings and several signing groups

         Constructing The Group Signature Scheme (GDS-3.1)

Suppose there is a signing group of m signers who want to sign the document M. Each of the signers selects a private key x. His/Her corresponding public key is 𝑦i = 𝛼^xi 𝑚𝑜𝑑 𝑝, 𝑖   = 1, 2, … , 𝑚. The public key 𝑌 of the group manager is a public key of the group and is calculated as follows 𝑌 = 𝛼^K 𝑚𝑜𝑑 𝑝, where 𝑋 is the manager’s private key. The group manager, can be a element in the PKI system. The value 𝑌 is used in the signature verification procedure of the GDS-3.1 scheme. Let 𝐹H is some specified hash function.

The group signature scheme based on factoring and discrete logarithm problems (GDS-3.1) is described as follows:

•    The group signature generation procedure on the document M

It consists of stages:

1.The group manager does the following tasks:

• Computes hash value from document 𝑀

𝐻 = 𝐹_H(𝑀)

• Calculates masking coefficients l_i:

l_i  = 𝐹H(𝐻 || 𝑦i|| 𝐹H(𝐻 ||𝑦i|| 𝑋))

Sends each value _i to the corresponding i–th group member

• Sends each value d_i to the corresponding i–th group member
• Computes the first element of the group signature 𝑈:

2.Each i-th signer in the signing group does the following tasks:

• Generates a random number 𝑘i, 𝑘i < 𝑛, anh then computes the value 𝑅_i:

𝑅i  = 𝛼^ki  𝑚𝑜𝑑 𝑝

Sends 𝑅ito the group manager

3.The group manager does the following tasks:

• Generates the random number 𝐾, 𝐾 < 𝑞, and then computes the values 𝑅′, 𝑅, 𝐸:

𝑅^‘ = 𝛼^K𝑚𝑜𝑑 𝑝

and

𝐸 = 𝐹H(𝑀||𝑅||𝑈) 𝑚𝑜𝑑 d

where d is a large prime, |d| = 160 bit.

• Sends value E to all signers in signing group

E is the second element of the group signature.

4. Each i-th signer in the signing group does the following tasks:

• Computes his/her shared signature 𝑆_i:

𝑆i  = (𝑘i  + 𝑥id_i𝐸)^1/2𝑚𝑜𝑑 𝑛

• Sends 𝑆_i to the group manager

5.The group manager does the following tasks:

• Verifies the correctness of each shared signature 𝑆􀯜 by checking equality:

𝑅i    =  𝛼^Si2 𝑦^–diE𝑚𝑜𝑑 𝑝

• If all signature shared signatures S_i satisfy the last verification equation, then he/she computes his shared signature:

• Computes the third element of the group signature 𝑆:

The tuple (𝑈, 𝐸, 𝑆) is a group signature of the signing group on the document M.

• The signature verification procedure on the document M

It includes the following steps (The verifier can be a element in the PKI system):

1. The verifier computes the hash function value from the document M:

𝐻 = 𝐹_H(𝑀)

     2.The verifier computes value 𝑅^∗:

𝑅   = 𝛼 ^s(𝑈𝑌)     𝑚𝑜𝑑 𝑝

3.The verifier computes value 𝐸^∗:

𝐸^∗ = 𝐹H(𝑀||𝑅^∗||𝑈) 𝑚𝑜𝑑 d

4.The verifier compares the values 𝐸^∗ with 𝐸. If 𝐸^∗ = 𝐸: The group signature is  valid; Otherwise, the

group signature is invalid. It is rejected.

• Proof of correctness of this signature scheme

To prove the correctness of this signatue scheme we only need to prove the existence of the equation

𝐸^∗ = 𝐸.

It is easy to see 𝑅^∗ = 𝑅. Indeed:

The correctness of the signature scheme has been proved.

3.2. Constructing the Collective Digital Signature For Several Signing Groups

Let 𝑔 signing groups with public keys 𝑌j = 𝛼^Kj  𝑚𝑜𝑑 𝑝, where 𝑗 = 1,2, … , 𝑔. 𝑋j  is the secret key of the j-th goup manager, have intention to sign the document 𝑀. Suppose also the j-th signing goup inclues 𝑚j active individual signers (persons appointed to act on behalf of the j-th signing goup).

The collective signature scheme for several signing group (RCS.01-3.2) is described as below.

• The collective signature generation procedure on the document M

It consists of stages:

1. Each j-th group manager in the signing collective does the following tasks:

• Based on the group signature generation procedure described above (section 3.1) to generals masking parameters 𝜆ji for the signers of j-th group.
• Computes the value 𝑈j (where 𝑖 = 1, 2, … , 𝑚j):

𝑈 as the shared element of the j-th group in the first element of the collective signature.

• Comutes the randomizing parameter 𝑅j:

• Sends values 𝑈j  and 𝑅j to all other group managers in the signing collective.

2.Each j-th group manager in the signing collective computes values 𝑈, 𝑅 and 𝐸:

𝑈 and 𝐸 are the first and second elements of the collective signature.

3.Each j-th group manager does the following tasks:

• Computes the shared signature of j-th group:

Where 𝑆_ji in the shared signature of the i-th signer in the j-th group,

• Sends 𝑆_j to other group managers in the signing collective.

4.Each j-th group manager does the following tasks:

• Can verify the correctness of each shared signature 𝑆_j by cheaking equality:

• If all shared signatures 𝑆j satisfy the last verification equation, then the third element S of the collective signature is computed:

The tuple (𝑈, 𝐸, 𝑆) is the collective signature on the document M of the signing collective there are 𝑔 signing groups.

• The signature verification procedure on the document M

It includes the following steps (The verifier can be a element in the PKI system):

1.The verifier computes the collective public key shared by all signing groups:

2.The verifier computes the value 𝑅^∗:

3.The verifier computes the value 𝐸^∗:

𝐸^∗ =  𝐹_H(𝑀||𝑅^∗||𝑈) 𝑚𝑜𝑑 d

4.The verifier Compares the values 𝐸^∗ with 𝐸. If 𝐸^∗ = 𝐸: The collective signature is valid. Otherwise, the collective signature is invalid. It is rejected.

•   Proof of correctness of this signature scheme:

To prove the correctness of this signatue scheme we only need to prove the existence of the equation

𝐸^∗ = 𝐸.

It is easy to see 𝑅^∗ = 𝑅. Indeed:

Since 𝑅^∗ = 𝑅 so 𝐸^∗ = 𝐸 (𝐸^∗ = 𝐹H(𝑀|| 𝑅^∗|| 𝑈) = 𝐹H(𝑀|| R|| 𝑈) = 𝐸) is always exists.

The correctness of the signature scheme has been proved.

Constructing the Collective Digital Signature Scheme for Several Individual Signers and Several Signing Groups

The collective signature generation procedure of this scheme is similar to that of the RCS.01-3.2 scheme, but for individual signers, 𝑈𝑗 is equal to 1.

Suppose 𝑥j and 𝑦j = 𝛼^xj, where 𝑗 = 𝑔 + 1, 𝑔 + 2, … , 𝑔 + 𝑚, are a private key and a public key, correspondingly, of 𝑚 individual signers participating in the protocol for generating the collective digital signature for g signing groups and m individual signers.

The collective signature scheme for 𝑚 individual signers 𝑔 signing groups (RCS.02-3.3) is described as below.

• The signature generation procedure on the document M

It consists of stages:

1. Each j-th group manager in the signing collective does the following tasks:

• Based on the group signature generation procedure described above (section 3.1) to generals masking parameters 𝜆ji for the signers of j-th group.

• Computes the value 𝑈j (where 𝑖 = 1,2, … , 𝑚j):

𝑈 as the shared element of the j-th group in the first element of the collective signature.

Computes the randomizing parameter 𝑅j:

• Send values 𝑈j and 𝑅j to all other managers and all individual signers in the signing collective.

2.Each j-th individual signer (𝑗 = 𝑔 + 1, 𝑔 + 2, … , 𝑔 + 𝑚) does the following tasks:

• Generates a random value 𝐾j, 𝐾j < 𝑛, and then computes the value 𝑅j:

Generates a random value 𝐾j, 𝐾j < 𝑛, and then computes the value 𝑅j:

𝑅j = 𝛼^Kj 𝑚𝑜𝑑 𝑝

Sent 𝑅j to all group managers and other individual signers in the signing collective.

Each j-th group manager and each j-th individual signer in the signing collective computes values 𝑈, 𝑅 and 𝐸:

where 𝛿 is a large prime having, |δ| = 160 bits; 𝑈 = 0 for 𝑗 = 𝑔 + 1, 𝑔 + 2, … , 𝑔 + 𝑚.

𝑈 and 𝐸 are the first and second elements of the signature.

3. a) Each j-th group manager computes the shared signature of j-th group 𝑆_j:

where 𝑆ji is the shared signature of the i-th signer in the j-th signing group.

And sends 𝑆j to all individual signers and other group managers.

b) Each j-th individual signer computes his/her shared signature 𝑆j:

And sends 𝑆j to all group managers and other individual signers.

4.Each j-th group manager and each individual signers does the following tasks:

• Can verify the correctness of each share signatures 𝑆j by checking equality:

If all shares Sj satisfy the last verification equation, then the third element Sof the collective signature is computed:

The tuple (𝑈, 𝐸, 𝑆) is the collective signature on the document M of the signing collective there are 𝑔 signing groups and 𝑚 individual signers.

The first element 𝑈 of the collective signature contains information about the all group members of each signing group who signed the document 𝑀.

•   The signature verification procedure on the document M

It includes the following steps (The verifier can be a element in the PKI system):

1.The verifier computes the collective public key shared by all signing groups and individual signers:

2.The verifier computes the value 𝑅^∗:

3.The verifier computes the value 𝐸^∗:

𝐸^∗ = 𝐹_H(𝑀|| 𝑅^∗|| 𝑈)

4.The verifier Compares the value 𝐸^∗ with 𝐸. If 𝐸^∗ = 𝐸: The collective signature is valid; Otherwise, the collective signature is invalid. It is rejected.

• Proof of correctness of this signature scheme:

To prove the correctness of this signatue scheme we only need to prove the existence of the equation

𝐸^∗ = 𝐸.

It is easy to see 𝑅^∗ = 𝑅. Indeed:

The correctness of the signature scheme has been proved.

4.SECURITY ANALYSIS AND PERFORMANCE EVALUATION

Security analysis of the proposed collective digital signature schemes

Security level of the single digital signature (SDS-2.1)

It is easy to see that, the solution of the discrete logarithm problem in 𝐺𝐹(𝑝) is not sufficient for breaking this signature scheme. To break the scheme it is required to know the factorization of n. Indeed, the solution of the discrete logarithm problem leads to the computation of the secret key x and the possibility to calculate the value 𝑘 + 𝑥𝐸 𝑚𝑜𝑑 𝑛. However, to calculate the signature element𝑆 is required to extract the 2-th root modulo n from 𝑘 + 𝑥𝐸 𝑚𝑜𝑑 𝑛. This requires factoring the modulus 𝑛. This is the second difficult problem.

Security level of the group digital signature scheme (GDS-3.1)

With the group signature scheme, there are two main types of attacks: Internal attacks and external attacks. In external attacks, the attacker only knows the system parameters and the public keys, along with the document M, while in internal attacks, the attacker will know a lot more information.

Let’s take a look at the most likely successful case where the attacker is the group manager, since he has the most information.

• Attack to reveal secret key:

Assuming the signing group consists of 𝑚 members. Since the group manager knows the values 𝑆m, 𝑅m, 𝑦m so if he wants to attack the m-th person in the signing group he can do the following: He needs to calculate: 𝑥m = 𝑙𝑜𝑔a 𝑦m 𝑚𝑜𝑑 𝑝; or computes: 𝑘m = loga 𝑅m 𝑚𝑜𝑑 𝑝; and then computes: 𝑥m = 𝑆² − 𝑥𝐸 𝑚𝑜𝑑 𝑛. These require solving the discrete logarithm problem.

•     Signature forgery attack:

Assuming the signing group consists of 𝑚 members. The group manager of this signing group knows the values 𝑆m, 𝑅m, 𝑦m so if the group manager wants to attack the m-th person in the signing group he perform the following steps:

Choose 𝑋 ∈ [1, 𝑛 − 1] and calculate his public key:

And calculate the common public value of group.

Choose 𝐾 ∈ [1, 𝑛 − 1] and compute:

Compute 𝑅 and 𝐸, send 𝐸 to all other member of group.

The tuple (𝑈, 𝐸, 𝑆) still satisfy the test equation 𝑅 = 𝛼^S2 (𝑈𝑌)^E 𝑚𝑜𝑑 𝑝. Because:

When deploying the scheme to prevent this type of attack, it is necessary to have a trusted department to act as the group manager. The PKI plays an important role in this case [21-22].

When building a signing group, that department is responsible for receiving the public key of each signing member, then calculating and publishing the public public key of the signing group, the public keys of the members must also be made public. Publicly announced in the signing group for all members of the group to know. The private-public keys of the members and the public keys of the whole group are fixed, and the attacker will not be able to recompute them as shown in expression (53). So the scheme is safe if implemented correctly (53).

The security level of the collective digital signature and the collective digital signature of signing groups are similar to Security level of digital signature for signing group we mention above.

• Performance evaluation of the proposed collective digital signature schemes

The performance of a digital signature scheme can be evaluated by calculating the time cost of signature generation and the time cost of signature verification. We do it this way. The time costs of representative collective signature schemes proposed in this paper are shown in Table 1.

Notations: 𝑇h: Time cost of a hash operation in 𝑍p; 𝑇s: Time cost of a scalar multiplication in 𝑍p;

𝑇_inv: Time cost of a inverse operation in 𝑍p; 𝑇e: Time cost of an exponent operation in 𝑍p; 𝑇_m: Time cost of a modular multiplication in 𝑍p. According to [23]: 𝑇_h ≈ 𝑇_m, 𝑇s ≈ 29𝑇_m, 𝑇inv ≈ 240𝑇_m,

Figure 1. Example of a Petri Net

Figure 1. Example of a Petri Net

Table 1 shows that the time cost for the generation of signature components and for the signature verification of the proposed collective signature schemes are is much higher than that of the similar signature scheme in [24]. This is considered as a limitation that needs to be overcome for schemes built on two difficult problems factoring and discrete logarithm [25-27].

5.  CONCLUSION

In this paper, we have shown that there is a new authentication requirement that requires collective key generation and signature generation algorithms to satisfy. Our proposed collective signature can meet this new requirement.

In addition, we have succeeded in using simultaneously two difficult problems factoring and discrete logarithm to build two types of representative collective signature schemes, which are: i) the collective signature scheme for many signing groups and ii) the collective signature scheme for many individual signers and many signing groups. These types of schemes are essential for the multi-level authentication requirements of many information exchange applications in today’s network environment and it is also easy to deploy on existing PKI systems.

The simultaneous combination of two difficult problems factoring and discrete logarithm is demonstrated by choosing a prime modulo p with a special structure, 𝑝 = 2𝑛 + 1 with

𝑛 = 𝑞′𝑞, 𝑞^‘ and 𝑞 are large prime numbers having the 512 bit size or 1024 bit. The security level of the proposed collective signature schemes is inherited from the base scheme which has been analyzed in section 4.1. That is, to break the proposed collective signature scheme, the attacker must also solve two difficult problems simultaneously.

The paper also calculated and compared the performance of the two proposed schemes with the performance of some other schemes.

CONFLICT OF INTEREST

The authors declare no conflict of interest.

REFERENCES

[1] Pieprzyk J., Hardjono T. & Seberry J., (2003) “Fundamentals of Computer Security”, Springer-Verlag, Berlin Heidelberg.
[2] National Institute of Standards & Technology, (2009) “Digital Signature Standard”, Federal Information Processing Standards Publication 186-3.
[3] Ganeshkumar K. & Arivazhagan D., (2014) “Generating A Digital Signature Based On New Cryptographic Scheme For User Authentication And Security”, Indian Journal of Science and Technology.
[4] Girault M., Poupard G. & Stern J., (2006) “On the Fly Authentication and Signature Schemes Based on Groups of Unknown Order”, In Journal of Cryptology, no.19, pp.463-487.
[5] Seetha R. & Saravanan R., (2016) “Digital Signature Schemes for group communication: A Survey”, International Journal of Applied Engineering Research, no.11, pp.4416–4422.
[6] Enache A. C., (2012) “About Group Digital Signatures”, Journal of Mobile, Embedded and Distributed Systems, no.4, pp.193–202.
[7] Alamélou Q., Blazy O., Cauchie S. & Ph. Gaborit, (2017) “A code-based group signature scheme”, Designs, Codes and Cryptography, vol.82, no.1-2.
[8] Moldovyan A. A. & Moldovyan N. A, (2014) “Group signature protocol based on masking public keys”,Quasigroups and related systems, no.22, pp.133–140. International Journal of Computer Networks & Communications (IJCNC) Vol.14, No.2, March 2022
132
[9] Xie R., Xu C., He C. & Zhang X., (2016) “A new group signature scheme for dynamic membership”, International Journal of Electronic Security and Digital Forensics, vol.8, no.4.
[10] Moldovyan N. A., Nguyen Hieu Minh, Dao Tuan Hung & Tran Xuan Kien, (2016) “Group Signature Protocol Based on Collective Signature Protocol and Masking Public Keys Mechanism”, International Journal of Emerging Technology and Advanced Engineering, no.6, pp.1–5.
[11] Rajasree R. S., (2014) “Generation of Dynamic Group Digital Signature”, International Journal of Computer Applications, no.98, pp.1–5.
[12] Moldovyan N. A., (2011) “Blind Collective Signature Protocol”, Computer Science Journal of Moldova, no.19, pp.80–91.
[13] Tahat N., Ismail E., and Ahmad R., (2009) “A New Blind Signature Scheme Based on Factoring and Discrete Logarithms,” International Journal of Cryptology Research, vol.1, no.1, pp.1-9.
[14] Minh N., Binh D., Giang N. & Moldovyan N. A., (2012) “Blind Signature Protocol Based on Difficulty of Simultaneous Solving Two Difficult Problems”, Journal of Applied Mathematical Sciences, vol.6, no.139, pp.6903-6910.
[15] Berezin A., Moldovyan N. A. & Victor S., (2013) “Cryptoschemes Based on Difficulty of Simultaneous Solving Two Different Difficult Problems”, Computer Science Journal of Moldova, vol.21, no.2, pp.280-290.
[16] Schnorr C. P., (1991) “Efcient signature generation by smart-cards”, In Journal of Cryptology, vol.4, no.3, pp.161-174.
[17] Camenisch J. L., Piveteau J. -M. & Stadler M. A., (1995) “Blind Signatures Based on the Discrete Logarithm Problem”, In: Advances in Crypology – EUROCRYPT’94 Proc, Lecture Notes in Computer Science, Springer-Verlag, Berlin Heidelberg New York, vol.950, pp.428–432.
[18] Moldovyan N. A. & Moldovyan A. A, (2010) “Blind Collective Signature Protocol Based on Discrete Logarithm Problem”, Int. Journal of Network Security, no.11, pp.106–113.
[19] Nimbalkar A. B., (2018) “The Digital Signature Schemes Based on Two Hard Problems: Factorization and Discrete Logarithm”, Advances in Intelligent Systems and Computing, Cyber Security. vol.729, pp.493.498.
[20] Moldovyan N. A., (2011) “Blind Signature Protocols from Digital Signature Standards”, Int. Journal of Network Security, no.13, pp.22–30.
[21] Selvakumaraswamy S. & Govindaswamy U., (2016) “Efficient Transmission of PKI Certificates using ECC and its Variants”, The International Arab Journal of Information Technology, vol.13, no.1, pp.38-43.
[22] Shivkumar S. and Umamaheswari G., (2015) “Efficient Transmission of PKI Certificates using Elliptic Curve Cryptography and its Variants”, The International Arab Journal of Information Technology, pp. 38-43.
[23] 21Popescu C., (1999) “Blind signature and BMS using elliptic curves”, Studia univ babes–bolyai, Informatica, pp.43-49.
[24] 22Tuan N. K., Van V.L., Moldovyan D. N., Duy H. N. & Moldovyan A. A., (2018) “Collective signature protocols for signing groups”, In Proc. Information Systems Design and Intelligent Applications. Advances in Intelligent Systems and Computing, India.
[25] 23Moldovyan N. A., (2008) “Digital Signature Scheme Based on a New Hard Problem”, Computer Science Journal of Moldova, no.16, pp.163–18.
[26] 24Lee J., Kim H., Lee Y., Hong S. M. & Yoon H., (2017) “Parallelized scalar multiplication on elliptic curves defined over optimal extension field”, International Journal of Network Security, vol.4, p.99-106.
[27] 26Chaum D., (1983) “Blind Signatures for Untraceable Payments”, Advances in Cryptology: Proc. of CRYPTO’82, Plenum Press, p.199–203.

AUTHORS

Tuan Nguyen Kim was born in 1969, received B.E., and M.E from Hue University of Sciences in 1994, and from Hanoi University of Technology in 1998. He has been a lecturer at Hue University since 1996. From 2011 to the present (2021) he is a lecturer at Sch ol of Computer Science, Duy Tan U  iversity, Da Nang, Vietnam. His main research interestsinclude Computer Network Technology and Information.

Nguyen Tran Truong Thien was born in 1997, received B.E from Duy Tan University in 2020. He has been a security researcher at Duy Tan University since February 2021. Hismain research interests include is Network Security, Information Security and Machine learning for Cybersecurity.

Duy Ho Ngoc was born in 1982. He received his Ph.D. in Cybersecurity in 2007 from LETI University, St. Petersburg, Rus ia Federation. He has authored more than 45 scientific articles in cybersecurity.

Nikolay A. Moldovyan is an honored inventor of Russian Federation (2002), a laboratory head at St. Petersburg Institute for Informatics and Automation of Russian Acade   y of Sciences, and a Professor with the St. Petersburg State Electrotechnical University. His research interests include computer security and cryptography. He has authored or co- authored more than 60 inventions and 220 scientific articles, books, and report . He received his Ph.D. from the Academy of Sciences of Moldova (1981).