# Fail-Stop Group Signature Scheme

Authors: Jonathan Jen-Rong Chen; Yi-Yuan Chiang; Wang-Hsin Hsu; Wen-Yen Lin
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In this study, a fail-stop group signature scheme (FSGSS) that combines the features of group and fail-stop signatures to enhance the security level of the original group signature is proposed. Assuming that FSGSS encounters an attack by a hacker armed with a supercomputer, this scheme can prove that the digital signature is forged. Based on the aforementioned objectives, this study proposes three lemmas and proves that they are indeed feasible. First, how does a recipient of a digitally signed document verify the authenticity of the signature? Second, when a digitally signed document is under dispute, how can the group’s manager determine the identity of the original group member who signed the document, if necessary, for an investigation? Third, how can one prove that the signature is indeed forged following an external attack from a supercomputer? Following an attack, the signature could be proved to be forged without exposing the key. In addition, the ultimate goal of the group fail-stop signature scheme is to stop using the same key immediately after the discovery of a forgery attack; this would prevent the attack from being repeated.


---

## Body

## 1. Introduction

Electronic documents are being increasingly used instead of paper to conduct official government and private business. Among other advantages, this benefits the environment by reducing the amount of paper being used. However, the use of electronic documents also increases the importance of using digital signatures to guarantee the validity, authenticity, and integrity of electronic documents and reduce the risk of documents being forged.To cope with the wide range of potential uses for digital signature technology, the concept of group signing was proposed. A real-life example is considered to illustrate the process of using a group fail-stop signature scheme. The chief of Taiwan’s Environmental Protection Administration, along with 19 other staff members of the agency, is eligible to digitally sign documents; these staff members include those accusing a subordinate unit of breaking the law. To safeguard the agency members’ neutrality and protect them from interference, each staffer is required to activate a digital signature key when they release a statement or document representing the administration. The recipient of the document would be able to verify the authenticity of the digital signature. However, in the event that someone impeaches the integrity or validity of a digitally signed document, the identity of the individual who originally signed the document would remain a secret.Companies or other entities cited for violations by the Environmental Protection Administration could file a complaint with the agency to deny that they had violated the law. As part of the review process, it might be necessary to determine the identity of the official who signed the original document making the accusation. Under the present scheme, only the manager in the group would have the ability to identify the person who signed the document. The manager, however, cannot pretend to be a member of another group to forge the digital signature.Chaum and Van Heyst [1] concluded that there are three properties of group signatures. (i) Only members of the group can sign messages. (ii) The recipient can verify that it is a valid group signature but cannot discover the group member who signed the message. (iii) If necessary, the signature can be “opened,” to reveal the person who signed the message.The group signature scheme also has some favorable features that make it applicable in a range of fields. A digital signature can ensure the validity and authenticity of electronic documents. If the possibility of a document being forged could be reduced, or even if it were possible to prove that the digital signature was forged, the security level of the digital signature could then be enhanced. Another type of fail-stop signature scheme (FSS) can satisfy the aforementioned requirements.Kitajima et al. [2] showed that an FSS has to have at least two security properties. (i) A scheme based on information-theoretic security has to be secure, even against a computationally unbounded adversary. (ii) If the computational assumption is broken, an honest signer should be able to prove that a signature is a forgery by virtue of information-theoretic security.In this work, a fail-stop group signature scheme (FSGSS) is proposed. FSGSS combines all the functions and features of two schemes: group signature (GS) and FSS. This algorithm integrates the features of the two types of digital signatures, which strengthens its security level under the GS system. The combination scheme ensures that the group members can prove that a digital signature is indeed a forgery after supercomputer forgery attacks.The remainder of this paper is organized as follows: Section2 describes studies related to the present work. Section 3 presents our scheme, and Section 4 provides an analysis of the scheme and a discussion thereof. Finally, Section 5 concludes the paper and provides directions for future research.


## 2. Related Work

Desmedt proposed a group-oriented cryptosystem concept in 1987. In his dissertation [3], he noted that, in addition to entities that exist as individuals, there are entities comprising groups of several individuals, such as hospitals, schools, public institutions, and private companies. When these entities issue signed electronic documents, such as certificates, the concept of a digital signature becomes a mechanism to replace signatures on paper documents. Digital signatures could be placed on electronic diplomas, electronic medical records, and other official documents released by governmental agencies. The documents that carry digital signatures must have the following features: certainty of identity, nonrepudiation, and unforgeability.Therefore, the design of the way keys are exchanged, the parameters of the exchanges become particularly important. Although each member in a group has a secret key, the group password must be reused. In other words, individuals in the group cannot exchange their keys during an operation. Instead, they exchange secondary keys derived from their main keys. This ensures the security of the main keys. In addition, members cannot export the group’s master key. This ensures that this key remains secure. Chen and Yuanchi [4] developed a new and fast anonymous digital signature system by linking the LUC function with the complexities of discrete logarithms and factorization.Conversely, multiple studies have focused on the security of conventional digital signature schemes that rely on a computational assumption. FSSS provide security for a sender against a forger with unlimited computational power by enabling the sender to provide a proof of forgery if it occurs. FSSs have been proposed in [5–10]. Chain [11] proposed that a fail-stop scheme could assert a victim’s innocence, without exposing the n=p×q secret, and would guard against malicious behavior. More recently, Kitajima et al. [2] proposed a framework for FSS operating in a multisigner setting and called for a primitive fail-stop multisignature scheme. In other words, they combined threshold and fail-stop signatures. After the first aggregate signature scheme was proposed, several researchers attempted to propose more efficient versions of FSS by combining various schemes.Recently, blockchain technology was used to realize the calculation and verification of the original GS algorithm. The calculation of the group certificate and signature recognition should be completed by the corresponding smart contract. This reduces the possibility of a joint attack. The newly added signature node no longer needs the approval of the center and only requires the approval of the majority node, realizing the true decentralization of signatures [12]. However, the decentralized GS scheme, based on blockchain, requires more calculation and is more expensive to implement smart contracts and applications without a decentralized network. Conversely, the blockchain-based smart contract is visible to all blockchain users. This leads to a situation where bugs, including security holes, are visible to all, yet may not be quickly fixed [13–15]. In particular, issues in Ethereum smart contracts include ambiguities and easy-but-insecure constructs in its contract language solidity, compiler bugs, Ethereum virtual machine bugs, attacks on the blockchain network, and the immutability of bugs; moreover, there is no central source documenting known vulnerabilities, attacks, and problematic constructs [14].


## 3. Proposed Scheme

### 3.1. Initialization

The system center (SC) chooses a primitive elementg over the Galois field p0, satisfying the following equation:(1)p0=4p1q1+1,where p1,q1 are large primitive. Let(2)n=p1q1.Then, SC chooses a numberg2∈Zn∗, satisfying(3)g2p1≡1modp0,where g2,p0,n and p1,q1 are the public key and secret key of the SC, respectively. The details of the initialization process are shown in 0 (Figure 1).Figure 1
Initialization of GFSS.


### 3.2. Group and Its Members

Without loss of generality, we assume a group and its membersui,0≤i≤l, where u0 is the manager of a group. The member registers to SC individually as follows:ui chooses a number xi and calculates(4)g2xi≡yimodp0,ui uses the yi to register.


### 3.3. Parameters Exchange

Example 1:ui,0≤i≤l, requests a part of the parameter from u0; and then, u0 chooses a number k and calculates(5)g2k≡r1modp0,(6)u0⟶ui:r1.This means thatu0 sends r1 to ui. ui chooses a number b′ and calculates(7)g2b′≡bmodp0,(8)r1b≡r3modp0,(9)r2≡r3bmodn,(10)ui⟶uo:r2,u0 chooses a number a, satisfying the following equation:(11)a≡x0r2+ksmodn,(12)u0⟶ui:a,s.After the aforementioned procedure is performed, if manageru0 knows the parameters, k,a,x0,andr2, then s is known. It is to be noted that y0,r1 is the public key of u0, where g2x0≡y0modp0, based on equation (4). The detailed process of GFSS is shown in 0 (three-way handshake for exchange parameters) (Figure 2).Figure 2
Three-way handshake for parameter exchange.


### 3.4. Signing Messagem

Multiplying both sides of equation (11) with b, we obtain(13)ba≡x0br2+kbsmodn.Multiplying both sides of equation (9) with b, we obtain(14)r3≡br2modn.Using equations (13) and (14), we obtain(15)ba≡x0r3+kbsmodn.Then, we choose two numbersc,e and calculate(16)g2c≡r5modp0,(17)g2e≡Emodp0.Let(18)r4≡r3r5modp0,and(19)s1≡r5smodn.Addingcs on both sides of equation (15), we acquire(20)ba+cs≡x0r3+kbs+cs≡x0r3+kb+csmodn.Usingr5 from equations (18) and (19) to multiply both sides of equation (20), we obtain(21)ba+csr5≡x0r4r5r5+kb+cs1r5r5≡x0r4+kb+cs1modn.Let(22)r6=ba+csr5modn,and(23)m+r6=cE+es2modn.Assuming that the recipient of the messageisR, ui sends messages to R. It is to be noted that(24)ui⟶R:m,c,E,r4,r6,s1,s2,where R is used in the equations as follows:(25)g2r6≡y0r4r4s1modn,(26)g2m+r6=g2cEEs2modp0.The receiver accepts this digital signature if both equations (25) and (26) are valid. Otherwise, this digital signature is denied (Table 1).Table 1
List of members holding parameters.
SCuouiRSCuouiRg2vvvvsvvpovvvvmvvnvvvvcvvyivvvEvvr1vvr4vvb′vr6vvbvs1vvr2vvs2vvavv


## 3.1. Initialization

The system center (SC) chooses a primitive elementg over the Galois field p0, satisfying the following equation:(1)p0=4p1q1+1,where p1,q1 are large primitive. Let(2)n=p1q1.Then, SC chooses a numberg2∈Zn∗, satisfying(3)g2p1≡1modp0,where g2,p0,n and p1,q1 are the public key and secret key of the SC, respectively. The details of the initialization process are shown in 0 (Figure 1).Figure 1
Initialization of GFSS.


## 3.2. Group and Its Members

Without loss of generality, we assume a group and its membersui,0≤i≤l, where u0 is the manager of a group. The member registers to SC individually as follows:ui chooses a number xi and calculates(4)g2xi≡yimodp0,ui uses the yi to register.


## 3.3. Parameters Exchange

Example 1:ui,0≤i≤l, requests a part of the parameter from u0; and then, u0 chooses a number k and calculates(5)g2k≡r1modp0,(6)u0⟶ui:r1.This means thatu0 sends r1 to ui. ui chooses a number b′ and calculates(7)g2b′≡bmodp0,(8)r1b≡r3modp0,(9)r2≡r3bmodn,(10)ui⟶uo:r2,u0 chooses a number a, satisfying the following equation:(11)a≡x0r2+ksmodn,(12)u0⟶ui:a,s.After the aforementioned procedure is performed, if manageru0 knows the parameters, k,a,x0,andr2, then s is known. It is to be noted that y0,r1 is the public key of u0, where g2x0≡y0modp0, based on equation (4). The detailed process of GFSS is shown in 0 (three-way handshake for exchange parameters) (Figure 2).Figure 2
Three-way handshake for parameter exchange.


## 3.4. Signing Messagem

Multiplying both sides of equation (11) with b, we obtain(13)ba≡x0br2+kbsmodn.Multiplying both sides of equation (9) with b, we obtain(14)r3≡br2modn.Using equations (13) and (14), we obtain(15)ba≡x0r3+kbsmodn.Then, we choose two numbersc,e and calculate(16)g2c≡r5modp0,(17)g2e≡Emodp0.Let(18)r4≡r3r5modp0,and(19)s1≡r5smodn.Addingcs on both sides of equation (15), we acquire(20)ba+cs≡x0r3+kbs+cs≡x0r3+kb+csmodn.Usingr5 from equations (18) and (19) to multiply both sides of equation (20), we obtain(21)ba+csr5≡x0r4r5r5+kb+cs1r5r5≡x0r4+kb+cs1modn.Let(22)r6=ba+csr5modn,and(23)m+r6=cE+es2modn.Assuming that the recipient of the messageisR, ui sends messages to R. It is to be noted that(24)ui⟶R:m,c,E,r4,r6,s1,s2,where R is used in the equations as follows:(25)g2r6≡y0r4r4s1modn,(26)g2m+r6=g2cEEs2modp0.The receiver accepts this digital signature if both equations (25) and (26) are valid. Otherwise, this digital signature is denied (Table 1).Table 1
List of members holding parameters.
SCuouiRSCuouiRg2vvvvsvvpovvvvmvvnvvvvcvvyivvvEvvr1vvr4vvb′vr6vvbvs1vvr2vvs2vvavv


## 4. Analysis and Discussion

In this section, we first introduce Lemma1 to check the validity of a digital signature. Lemma 2 verifies whether a digital signature is activated by a group member. Lemma 3 shows that the attack method, mentioned by Susilo [7], will not succeed. There are several parameters after these procedures. We created a list of members holding parameters, as shown in 0. In this scheme, the members share partial parameters and maintain a few parameter(s). For example, manager u0 holds only parameter k; member ui only holds parameter b. In this case, someone creates a digital signature of u0 and passes the verification; however, she/he is unaware of parameter b. That is, this person is a forger.Lemma 1.
Ifu0andui are trusted authorities, then both equations (24) and (25) are valid.Proof:.
Using equation (22), we have(27)g2r6≡g2ba+csr5≡g2x0r4+kb+cs1≡g2x0r4g2kb+cs1modn.
There are two parts of the last term of the aforementioned equations; considering the first part and using equation (4), we have(28)g2x0r4≡g2x0r4≡y0r4modn.
Considering the second part,(29)g2kb+cs1≡g2kbs1g2cs1≡g2kbs1g2cs1≡r1bs1g2cs1via equation5≡r1bs1g2cs1≡r1bs1r5s1via equation17≡r3s1r5s1≡r3r5s1via equation8≡r4s1modnvia equation18.
By combining equations (28) and (29), we obtain(30)g2r6≡y0r4r4s1modn.
Hence,(31)g2m+r6=g2cEEs2modp0.
Therefore, both equations (25) and (26) are valid.
Certain parameters are required to check whether messagem has been sent by ui. Hence, we obtain the following lemma:Lemma 2.
Ifu0andui are trusted authorities, then it implies that message m was sent from ui by equation (8).Proof:.
The following should be noted:(a)
r1b≡r3modp0 from equation (8)(b)
ui⟶R:m,c,E,r4,r6,s1,s2 from equation (24)(c)
u0⟶ui:a,s from equation (12)(d)
r4≡r3r5modp0 from equation (18)(e)
ba≡x0r3+kbsmodn from equation (15)(f)
g2k≡r1modp0 from equation (5)(g)
g2r6≡y0r4r4s1modn from equation (25)(h)
g2m+r6=g2cEEs2modp0 from equation (26)
Considering equation (19), s1≡r5smodn, s1ands can be determined because of equations (12) and (24). Hence, we can obtain r5 and r3 via equations (18) and (24). Finally, b must be calculated (only ui knows this parameter) because u0 is unaware of b.
Considering equation (15), a,x0,r3,k, and s are known. It is not easy for anyone to obtain b;only the manager of groupu0 knows this value. In fact, it is a discrete logarithm problem when someone knows r1,r3 only by equation (8).
We conclude thatu0 can obtain b because u0 already knows parts of parameters from ui and has their own parameter k. Therefore, after checking equations (25) and (26), we can say that the message is sent by ui.Lemma 3.
An attacker intercepting the message passed by the digital signature to adapt the method of Susilo et al. will not succeed.Proof:.
The following is to be noted:(a)
ui⟶R:m,c,E,r4,r6,s1,s2 from equation (24)(b)
g2r6≡y0r4r4s1modn from equation (25)(c)
g2m+r6=g2cEEs2modp0 from equation (26)
If an attacker A intercepts the message as shown in equation (24) because A is unaware of parameters x0,r4, we assume that(32)g2x0′≡y0modp0,g2r4′≡r4modp0.
Attacker A can easily forgem∗ for suitable parameters c′,E′,s2′ such that both equations (25) and (26) are valid. In other words, the digital signature passes the test of Lemma 2. After the procedure of Lemma 2 is performed, a nontrivial factor of n can be found by computing GCDb,b∗,n. We note that the probability of b being equal to b∗ is 1/q0. Therefore, it is proved that m∗ is not sent by the group members.


## 5. Conclusions and Future Work

In this study, we propose a novel FSGSS. This algorithm integrates the features of two types of digital signature, which strengthens its security level under the GS system. The proposed FSGSS ensures that the group members can prove that a digital signature is indeed a forgery after supercomputer forgery attacks. In addition to discussing the integration of these two digital signatures, this dissertation highlights three proposed Lemmas and proves that they are feasible. Lemma1 verifies an FSGSS digital signature. Lemma 2 is used by the group manager, when needed, to determine the identity of the group member who originally created the digital signature. Finally, this dissertation proposes Lemma 3. When the digital signature is found to be forged, members of the group can prove this fact.The ultimate goal of the group fail-stop signature scheme is to stop using the same key immediately after the discovery of a forgery attack; this would prevent the attack from being repeated. That is, the “key” considered in this study is parameterb used by ui. If the parameters need to be changed each time an entity is under attack, the process of replacing the parameters is equivalent to reexecuting the exchange parameter program. Therefore, in future work, we plan to design a scheme wherein we need not directly expose key b; we can then prove that a certain number of signatures are forged, which will enhance the efficiency of GFSS.



---

*Source: 6693726-2021-02-09.xml*