Computers, Materials & Continua DOI:10.32604/cmc.2022.024677 | |

Article |

New Representative Collective Signatures Based on the Discrete Logarithm Problem

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

2Department of Information Technology, Ha Noi, Vietnam

3ITMO University, St. Petersburg, Russia

*Corresponding Author: Tuan Nguyen Kim. Email: nguyenkimtuan@duytan.edu.vn

Received: 27 October 2021; Accepted: 10 December 2021

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

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)

This part uses the digital signature scheme described in [10] as the basic scheme to build a collective signature scheme on document M for a collective consisting of m signers. Secret key

The input parameters are chosen as follows: Choose a sufficiently large prime number

The main procedures of the collective signature scheme on the document M are described below.

• The procedure for generating the collective digital signature on the document M

Includes the following stages:

1. Each j-th signer performs the following steps:

– Choose a random value

– Calculate the value of the random component

– Send

2. A certain signer, or all signers, in the signing collective does:

– Calculate the value of the common (public) random component of the collective R using the following formula:

– Calculate the first component E of the collective signature using the following formula:

where

3. Each j-th signer goes on to:

–Calculate the value of the individual share component

– Send

4. A certain person, or all signers, in the signing collective calculates the second component of the S collective signature using the following formula:

So the value pair (E, S) is the collective signature of the signing collective consisting of m signers on document M.

• The procedures for verification the collective digital signature on the document M

To verificate the validity of the signature received with the document M, the verifier performs the following step:

1. Calculate the public key y using the following formula:

2. Calculate the value of the random parameter R* using the following formula:

3. Calculate the value of the component 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.

• Proof of the correctness of the CDS-2.1 scheme:

To prove the correctness of this scheme, we need to prove the existence of the test expression

Conspicuously, the test expression

as

Thus, the test expression

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 key

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 document M, made by a collective of m individual 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 document M:

1.1. Each i signer generates a random number ti, ti < r, and then computes

Then send

1.2. Any signer in the group, or all, calculate

And calculate

where:

1.3. Each i signer calculate the personal share value

Then, sends

1.4. Any signer in the signing group, or all, calculate

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:

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 parameter

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 signature

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 expression

And calculates:

Thus, the expression

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:

Suppose that the j-th group consists of

The protocol of collective signatures for signing groups is descibed as follows:

• The procedure for generating the collective digital signature for

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

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

– Send

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

– Verify the precision of the shared component

– If all

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

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

1. Calculate collective public key

2. Calculate the

3. Calculate the

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 formula

b) Prove the correctness of the last signature:

Conspicuously, the signature check expression

as

Thus, the expression

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 of g signing groups and m individual signers, and want to create a representative collective signature on the document M. Assume that the j-th signing group consists of m signing members (

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 send

–

1b. Each j-th:

– Choose a random number

– Send

2. A GM or an individual signer in the collective calculates the values of R and

where:

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

–Calculate the shared component

– Send

3b. Each j-th individual signer

– Calculate their shared component

– Send

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

– Check the validity of each

with

with

– 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 of g signing groups and m individual 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

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 parameters

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:

According to [15]:

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.

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

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

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.

1. National Institute of Standards and Technology, “Digital signature standard,” in FIPS Publication 186-3, 2009. [Google Scholar]

2. J. Pieprzyk, T. Hardjono and J. Seberry, Fundamentals of Computer Security. Berlin: Springer-Verlag, 2003. [Google Scholar]

3. K. Itakura and K. Nakamura, “A public key cryptosystem suitable for digital multisignatures,” NEC Research and Development, vol. 71, pp. 1–8, 1983. [Google Scholar]

4. J. L. Camenisch, J. M. Piveteau and M. A. Stadler, “Blind signatures based on the discrete logarithm problem,” in Proc. Advances in Cryptology–EUROCRYPT'94, Lecture Notes in Computer Science, vol. 950, Berlin Heidelberg New York, Springer-Verlag, pp. 428–432, 1995. [Google Scholar]

5. D. Chaum, “Blind signatures for untraceable payments,” in Proc. Advances in Cryptology–CRYPTO’82, Plenum Press, pp. 199–203, 1983. [Google Scholar]

6. Q. Alamélou, O. Blazy, S. Cauchie and P. Gaborit, “A Code-based group signature scheme,” Designs, Codes and Cryptography, vol. 82, no. 1–2, 2017. [Google Scholar]

7. R. Xie, C. Xu, C. He and X. Zhang, “A new group signature scheme for dynamic membership,” International Journal of Electronic Security and Digital Forensics, vol. 8, no. 4, 2016. [Google Scholar]

8. A. A. Moldovyan and N. A. Moldovyan, “Group signature protocol based on masking public keys,” Quasigroups and Related Systems, vol. 22, pp. 133–140, 2014. [Google Scholar]

9. N. A. Moldovyan, N. H. Minh, D. T. Hung and T. X. Kien, “Group signature protocol based on collective signature protocol and masking public keys mechanism,” International Journal of Emerging Technology and Advanced Engineering, vol. 6, no. 6, pp. 1–5, 2016. [Google Scholar]

10. N. K. Tuan, V. L. Van, D. N. Moldovyan, H. N. Duy and A. A. Moldovyan, “Collective signature protocols for signing groups,” in Proc. Information Systems Design and Intelligent Applications. Advances in Intelligent Systems and Computing, India, 2018. [Google Scholar]

11. N. A. Moldovyan and A. A. Moldovyan, “Blind collective signature protocol based on discrete logarithm problem,” International Journal of Network Security, vol. 11, no. 2, pp. 106–113, 2010. [Google Scholar]

12. N. K. Tuan, H. N. Duy and N. A. Moldovyan, “Collective signature protocols for signing groups based on problem of finding roots modulo large prime number,” vol. 13, no. 4, pp. 59–69, 2021. [Google Scholar]

13. N. K. Tuan, H. N. Duy and N. A. Moldovyan, “Constructing the 2-element AGDS protocol based on the discrete logarithm problem,” International Journal of Network Security & Its Applications, vol. 13, no. 4, pp. 13–22, 2021. [Google Scholar]

14. H. Yong, C. Fugui and Q. Peixin, “Research on digital signature based on digital certificate,” in Proc: Proc. of 14th Youth Conf. on Communication, Scientific Research, pp. 467–470, 2009. [Google Scholar]

15. C. Popescu, “Blind signature and BMS using elliptic curves,” Studia Univ Babes–Bolyai, Informatica, pp. 43–49, 1999. [Google Scholar]

16. A. A. Bolotov, S. B. Gashkov and A. B. Frolov, “Elementary introduction to elliptic curve cryptography,” in Cryptography Protocols on the Elliptic Curves, KomKniga, Moskow, 2006. [Google Scholar]

17. D. Johnson, A. J. Menezes and S. Vanstone, “The elliptic curve digital signature algorithm,” Certicom, 2001. [Google Scholar]

18. Government Committee of the Russia for Standards, “GOST R34.10-2012: Russian Federation Standard,” Cryptographic Data Security, Produce and Check Procedures of Electronic Digital Signature, 2012. [Google Scholar]

19. A. Beresneva, A. Epishkina, O. Isupova, K. Kogos and M. Shimkiv, “Special digital signature schemes based on GOST R 34.10-2012,” in Proc: Electrical and Electronic Engineering Conf. (EIConRusNW), IEEE NW Russia Young Researchers, 2016. [Google Scholar]

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. |