Open Access

ARTICLE

# Constructing Representative Collective Signature Protocols Using The GOST R34.10-1994 Standard

1 School of Computer Science, Duy Tan University, Danang, Vietnam

2 Department of Information Technology, Hanoi, Vietnam

3 ITMO University, St. Petersburg, Russia

* Corresponding Author: Tuan Nguyen Kim. Email:

*Computers, Materials & Continua* **2023**, *74*(1), 1475-1491. https://doi.org/10.32604/cmc.2023.029253

**Received** 28 February 2022; **Accepted** 06 April 2022; **Issue published** 22 September 2022

## Abstract

The representative collective digital signature, which was suggested by us, is built based on combining the advantages of group digital signature and collective digital signature. This collective digital signature schema helps to create a unique digital signature that deputizes a collective of people representing different groups of signers and may also include personal signers. The advantage of the proposed collective signature is that it can be built based on most of the well-known difficult problems such as the factor analysis, the discrete logarithm and finding modulo roots of large prime numbers and the current digital signature standards of the United States and Russian Federation. In this paper, we use the discrete logarithmic problem on prime finite fields, which has been implemented in the GOST R34.10-1994 digital signature standard, to build the proposed collective signature protocols. These protocols help to create collective signatures: Guaranteed internal integrity and fixed size, independent of the number of members involved in forming the signature. The signature built in this study, consisting of 3 components (U, R, S), stores the information of all relevant signers in the U components, thus tracking the signer and against the “disclaim of liability” of the signer later is possible. The idea of hiding the signer’s public key is also applied in the proposed protocols. This makes it easy for the signing group representative to specify which members are authorized to participate in the signature creation process.## Keywords

As is known, digital signatures (DS) [1] are a key component of digital authentication systems [2]. Therefore, in order to have an authentication system that meets the specific requirements of a certain practical application, we must first build a corresponding digital signature. More precisely, it is necessary to build a DS scheme (DSS) that helps to create the desired digital signature.

Currently, many types of digital signatures have been researched and published such as single digital signatures (SDS), group digital signatures (GDS) [3–6], collective digital signatures (CDS) [7–9], single-blind digital signatures [10,11], blind collective digital signatures (BCS) [12], representative collective digital signatures (RCS) [9], … The SDSs is used to authenticate a particular personal. Meanwhile, GDSs, CDSs and RCSs are used to authenticate a signing group of many members [13,14]. The difference between a RCS and a GDS and a CDS is that it is formed from group digital signatures of many different signing groups. These signing groups may have no members at all, in which case the group leader can be viewed as personal signers. The RCS fulfils the authentication requirement for the multi-functional collectives. It is a new form of authentication, which is now quite common in e-commerce applications operating in the environment of Internet.

The DSS is usually built based on one of three common difficult problems such as factor analysis problem, discrete logarithmic problem on finite prime fields [15,16], discrete logarithmic problem on Elliptic curve [17,18]. At present, there are also some newly proposed difficult problems such as the problem of finding the modulo roots of large primes [19], the discrete logarithmic problem on the ring of residual classes, the discrete logarithmic problem on the two-dimensional non-circular subgroup.

The above mentioned difficult problems are the basis for a number of standard single-digital signature schemes, which are RSA (Rivest–Shamir–Adleman) [20] signature scheme, Schnorr’s signature scheme and ElGamal signature scheme. Some countries such as United States, Russian Federation or Belarus also rely on existing difficult problems to build their own digital signature standards or digital signature scheme standards. United States’s digital signature scheme standards include DSS (Digital Signature Standard) and DSA (Digital Signature Algorithm). Similarly, Russian Federation has digital signature scheme standards such as GOST R34.10-1994 [21], GOST R34.10-2001 [21] and GOST R34.10-2012 [22]. These signature scheme standards not only inherit the level of security of the difficult problem it uses, but also have enhanced security features brought about by the scheme’s own internals.

In this paper, we use the GOST R34.10-1994 standard (GOST-1994) [21], developed based on the logarithmic problem on prime finite field, to suggest two types of RCS scheme: (i) the CDS is shared by many signing groups and (ii) the CDS is shared by many signing groups and many personal signers. First, we use the single signature scheme built by this standard to build a CDS for a signing collective of

The security advantages and time costs of the proposed RCS schemes are analyzed, calculated and shown at the end of this paper.

2 The Related Basis Digital Signature Schemas

The following, the GOST-1994 of the Russian Federation will be used to develop two basic schemas: The CDS schema (in 2.1) and the GDS schema (in 2.2). In the GDS schema, the public key of the signing group member is hidden by masking techniques. These schemas will be used to build RCS schemas.

2.1 The Collective Digital Signature Schema According to The GOST R34.10-1994 Digital Signature Standard (The CDS-2 Schema)

The common parameters are similar to those defined for GOST-1994 [21].

Assuming there are

• The algorithm to create CDS on M:

Includes the following stages:

1. Each signer selects random number

and sends (broadcasts)

2. It is calculated the first element of the CDS:

The values R is broadcasted to the other signers.

3. Each signer computes its signature share

to the message M and the value R as follows:

4. Calculate the second element of the CDS:

The (R, S) number pair is the CDS on M.

The signature verifier does the following:

Input:

Output:

[1]. If (

Return False

[2].

[2.1].

[3].

[4].

[5]. If

Return True

Else

Return False

If

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

Substituting the value

So

2.2 The Group Digital Signature Schema According to The GOST R34.10-1994 Digital Signature Standard (The GDS-2 Schema)

Assuming there is a signing group that wants to create a GDS on the message M. Private key and public key of i-th signer be

Private key and public key of the group manager be

In this schema, the group manager’s internal public key is used, which is a number pair (n, e) and is generated as follows: (1)

The generalized scheme of the proposed group signature protocol includes the following steps [6,7]:

i) Considering the message M to be signed the group manager masks the public keys of the assigned signers. To mask the public key

ii) Using

iii) The group manager verifies the shared value of all assigned members and calculates his shared value in the group signature. Then he/she calculates the group signature as triple

It consists of stages:

1. The group manager does the following tasks:

- Computes hash value from message

- Calculates masking coefficients

- Sends each value

- Computes the first element of the group signature

2. The i-th signer does as follow:

- Randomly choose a number

- Sends

3. GM does as follow:

- Randomly choose a number

4. The i-th signer does as follow:

- Calculates his/her shared value,

- Sends

5. GM does as follow:

- Verifies the correctness of each

- If all signature shared signatures Si satisfy the last verification equation, then he/she computes

his shared signature:

- Calculates the third element of GDS,

The tuple

Done by signature verifiers:

Input:

Output:

[1]. If (

Return False

[3].

[4].

[5]. If

Return True

Else

Return False

If

If

Conspicuous:

Since

3 Constructing The New CDS Protocol Using The GOST R34.10-1994 Digital Signature Standard

The following, we use the CDS schema and the GDS schema built above to construct two types of RCS schemas [9]:

i) The CDS schema (type 1): This scheme helps to create a DS that deputize for a signing collective whose members are representatives, they are group leaders, for different signing groups.

ii) The CDS schema (type 2): This scheme helps to create a DS that deputize for a signing collective whose membership consists of two groups of members: That is, people who represent different signing groups. And, personal signers. These people do not belong to any sign group, they are also considered group representatives, but their group has no members.

3.1 The CDS Schema For Signing Groups (RCS.01)

Let

Suppose also the j-th signing group includes

The CDS scheme for signing groups (RCS.01) is as below.

It include of steps:

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

- Based on the group signature generation procedure described above (Section 2.2) to generals masking parameters

- Computes the value

- Computes

- Sends values

2. Each j-th group manager in the signing collective computes values

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

- Computes the shared signature of j-th group:

where

- Sends Sj 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

- If all shared signatures

The tuple

Input:

Output:

[1]. If (

Return False

[2].

[2.1].

[3].

[4].

[5]. If

Return True

Else

Return False

If

If we prove the existence of calculation formulas

We see

3.2 The CDS Schema For Signing Groups And Personal Signers (RCS.02)

The CDS schema in 3.2 is similar to RCS.01, but for signing groups and personal signers. In this case, the personal signer is treated as a signing group, but this group has no members, only the group manager. So

Suppose

Input parameters, public keys, and private keys are as in the CDS-02 diagram and the GDS-02 diagram. The CDS scheme for

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 2.2) to generals masking parameters

- Computes the value

- Computes

- Send values

2. Each j-th personal signer

- Generates a random value

- Sent

- Each j-th group manager and each j-th personal signer in the signing collective computes values

where

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

where

And sends

b) Each j-th personal signer computes his/her shared signature

And sends

4. Each j-th group manager and each personal signers do the following tasks:

- Can verify the correctness of each share signatures

For

For

- If all shares

The tuple

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

Input:

Output:

[1]. If (

Return False

[2].

[2.1].

[3].

[4].

[5]. If

Return True

Else

Return False

If

If we prove the existence of calculation formulas

i) Conspicuously, the formula

ii) Conspicuously, the formula for checking the shared signature

Indeed:

iii) Same as above,

Indeed:

Since

4 Security Analysis And Performance Evaluation

4.1 Resistance to Attack of The New CDS Schemas

CDS schemes can be attacked by people who are not members of the signing collective (known as external attacks) or by people who are members of the signing collective (known as internal attacks), it happens more often. In this section we will analyze the two most common types of internal attacks. Specifically, the CDS-02 scheme is resistant to the following two types of attacks:

Assuming that they are able to do this. Thus, under our assumption the collective forger (i.e., the considered n – 1 users) is able to figure out the CDS (R*, S*) respectively to public key

The CDS satisfies the following relation:

The last means that (R*, S*) is a personal DS of the nth user. Thus, we have formally proved that possibility to forge the CDS leads to possibility to forge the personal DS corresponding to the DS algorithm used in the protocol. In other words the CDS protocol is not less secure against the forgery attack than the used DS algorithm. Since GOST-1994 algorithm is secure the considered collective signature protocol is also secure (We consider GOST 34.10-1994 as a secure DS algorithm since it has been widely investigated and used in practice).

Attackers can generate values

Using designation:

From (32) and (33) we get:

where

This means that the attackers have get the collective signature value (R, S) that corresponds to n signers, the nth signer owning the public key

Thus, the attackers have calculated the secret key of the nth user using his personal DS, i.e., it is formally proved that if the CDS protocol is insecure, then the underlying DS algorithm is also insecure (in other words, the CDS protocol is not less secure than the underlying DS algorithm).

The RCS schemes proposed in this article use the CDS scheme as the basic scheme, so it is resistant to these two types of internal attacks.

4.2 Security Advantages of The New CDS Schemas

• We use GOST-1994 to build the RCS schemes, so basically these schemes have all the security advantages that the discrete logarithm problem over prime finite fields and this signature standard provides.

• The collective signature scheme, the CDS-02 scheme, has the following two outstanding security advantages: (i) Any illegal actions on generating the values

It is easy to show that the constructed representative collective signature schemes also have these security advantages.

• The group signature scheme GDS-02 has the following characteristics: The technique of “masking” the signing group member’s public key is used to ensure the privacy of the signer; Information of all signers is contained in the U component. When a signature dispute occurs, the group manager can completely resolve it thanks to the information stored in this component; The request for mutual authentication between the members of the signing group and the group manager can be done through the formula to generate the

4.3 Performance of The New CDS Schemas

This cost of RCS schemas in this article are shown in Tab. 1. For details on the information in this table see [24]; For the notations and conventions in this table see [25].

Tab. 1 shows that the time cost to create and to verify the signature of the RCS schema in this article is not much more extensive than compared to CDSs in [8].

• Obviously, until now, only the representative collective digital signatures and the representative digital signature schemes can meet the requirement of authentication based on a single digital signature, that is, only one-time authentication, for all members in multi-level functional signing collectives. Members of this signing collective include: (i) People representing different signing groups, they are called group leaders, and (ii) Single signers, but acting as group leaders. This is why the representative collective signature is formed in two steps: First, the group leader of each group signs together with their members to create the group signature of that signing group. Then, all group’s leaders and personal signers in the signing collective will together create a RCS of the signing collective. Subsequent authentication is based solely on this final signature.

• Since the group leader uses the secret key

• The formulas for generating

• The limitation of these new RCSs is the increase in the size of the signature. This limitation can be overcome if there is some signature scheme that helps to create a representative collective signature consisting of only two components but still contains the information of all the people who participated in the creation of this signature.

In this paper, first, we use GOST-1994 digital signature standard to build a CDS scheme and a GDS scheme. We then use these two schemes as the basis for building the proposed CDS schemes and protocols: (i) CDS for multiple signing groups; (ii) CDS for multiple signing groups and multiple personal signers. The RCSs are created on digital message M consisting of three components

The article also shows that the collective digital signature protocol built according to GOST-1994 digital signature standard is capable of resisting two common types of inside attacks: (i) Attacks on the secret key of signing group members; (ii) Forging the signature of a member of the signing group. With the GDS scheme, the public key “masking” technique, through the

The results obtained in this study show that the representative collective signature (RCS) has high feasibility and an acceptable level of security. However, because GOST-1994 is formed on the basis of the discrete logarithm problem on finite prime fields so there are some limitations that can be overcome if the scheme is formed according to the GOST R34.10-2001 digital signature standards or the GOST R34.10-2012 digital signature standards. This is our future work.

Funding Statement: This article is supported by Duy Tan University, Da Nang, Vietnam.

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

## References

- S. Radack, Updated digital signature standard approved as Federal Information Processing Standard (FIPS) 186-3, National Institute of Standards and Technology: FIPS Publication, pp. 183–186, 2009.
- J. Pieprzyk, T. Hardjono and J. Seberry, Fundamentals of computer security, Berlin: Springer-Verlag, 2003.
- D. Chaum and E. Heyst, “Group signatures,” in Advances in Cryptology-EUROCRYPT’ 91. Springer-Verlag, pp. 257–265, 1991.
- 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, pp. 332–351, 2016.
- Q. Alamélou, O. Blazy, S. Cauchie and Ph Gaborit, “A code-based group signature scheme,” Designs Codes and Cryptography, vol. 82, no. 1–2, pp. 469–493, 2017.
- A. A. Moldovyan and N. A. Moldovyan, “Group signature protocol based on masking public keys,” Quasigroups And Related Systems, vol. 22, no. 1, pp. 133–140, 2014.
- 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.
- 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, Springer, vol. 672, pp. 200–208, 201
- 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,” International Journal of Network Security & Its Applications, vol. 13, no. 4, pp. 59–69, 2021.
- 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, Berlin, Heidelberg, New York, Springer-Verlag, vol. 950, pp. 428–432, 1995.
- D. Chaum, “Blind signatures for untraceable payments,” in Proc. Advances in Cryptology–CRYPTO’82, Plenum Press, pp. 199–203, 1983.
- 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.
- K. Itakura and K. Nakamura, “A public key cryptosystem suitable for digital multisignatures,” NEC Research and Development, vol. 71, pp. 1–8, 1983.
- D. M. Tuan, “New elliptic curve digital multi-signature schemes for multi-section messages,” in Proc. Int. Conf. on Computing and Communications Technologies Research-Innovation and Vision for the future, Vietnam, pp. 25–28, 2012.
- D. Poulakis and R. Rolland, “A digital signature scheme based on two hard problems,” in Computation, Cryptography, and Network Security, Springer, pp. 441–450, 20
- N. A. Moldovyan, “Digital signature scheme based on a new hard problem,” Computer Science Journal of Moldova, vol. 16, no. 2, pp. 163–182, 2008.
- 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.
- R. L. B. Daniel, “Generic groups, collision resistance, and ECDSA,” ACM journal: Designs, Codes and Cryptography, vol. 35, no. 1, pp. 119–152, 2005.
- N. A. Moldovyan and V. A. Shcherbacov, “New signature scheme based on difficulty of finding roots,” Quasigroups and Related Systems, vol. 20, no. 1, pp. 261–266, 2012.
- M. Punita and M. Sitender, “RSA and its correctness through modular arithmetic,” in Int. Conf. On Methods And Models In Science And Technology, ICM 2st-10, AIP Conf. Proc. 1324, pp. 463–466, 2010.
- A. Komarova, A. Menshchikov and T. Klyaus, “Analysis and comparison of electronic digital signature state standards GOST R34.10-1994, GOST R34.10-2001 and GOST R34.10-2012,” in Proc: the 10th Int. Conf., Jaipur, India, 2017.
- 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.
- 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.
- T. N. Kim, D. H. Ngoc and N. A. Moldovyan, “Constructing collective signature schemes using problem of finding roots modulo,” Computers, Materials & Continua, vol. 72, no. 1, pp. 1105–1122, 2022.
- C. Popescu, “Blind signature and BMS using elliptic curves, Studia univ babes–Bolyai, Informatica, pp. 43–49, 1999.

## Cite This Article

T. N. Kim, D. H. Ngoc and N. A. Moldovyan, "Constructing representative collective signature protocols using the gost r34.10-1994 standard,"*Computers, Materials & Continua*, vol. 74, no.1, pp. 1475–1491, 2023.