# A New Code-Based Linkable Threshold Ring Signature Scheme

Authors: Fang Ren; Haiyan Xiu; Chuxin Ji; Dong Zheng; Ziyi Wu
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

In this paper, we construct a new code-based linkable threshold signature scheme whose security is based on the hardness of the syndrome decoding problem and general syndrome decoding problem. We show that our scheme is secure in terms of existential unforgeability, anonymity, nonslanderability, and linkability. The complexity of the signature size proposed in this paper isOt. Our method is particularly well suited for large free group voting systems. The greater the number of members in the ring, the more pronounced the advantage of the signature length is when compared to other schemes. That is, our scheme achieves a fixed length signature, independent of the number of ring members. In addition, our scheme has a very short public key, and the size is ON.


---

## Body

## 1. Introduction

The ring signature scheme is a special type of digital signature that was presented in 2001 by Rivest et al. [1]. It may also be regarded as a generalization of group signatures, while it varies from group signatures [2] in that ring signatures do not have a group administrator. Ring signature schemes enable a ring member to sign a message on the ring’s behalf while maintaining the anonymity of this ring’s members. In other words, although the actual message’s signer is unknown to the verifier, the verifier is aware that the signer belongs to this ring.However, in some applications, such as e-voting, in order to limit the ability of an individual to sign,t members must be willing to cooperate to generate a valid signature. Bresson et al. [3] used the notion of partitioning and combining functions to extend the ring signature scheme into a threshold ring signature scheme. A subset of t-out-of-N users in such a scheme cooperates to construct a signature while keeping the identity of the subgroup of t users secret.The first effective code-based threshold ring signature system was proposed by Melchor et al. [4]. Comparatively speaking, to other threshold ring signature schemes based on number theory, this scheme is designed based on the coded-Stern’s signature protocol, which is extremely quick and resistant to quantum attacks. The complexity of the signature length in this scheme is ON. The hardness of the q-ary syndrome decoding problem was used by Cayrel et al. [5] to construct a code-based threshold ring signature scheme in 2012. A zero-knowledge identification protocol based on coding theory called AGS was the foundation for the threshold ring signature scheme introduced by Assidi et al. [6] in 2019. This scheme utilizes a double circulant code, which reduces the size of the public key. At the same time, the cheating probability of the AGS protocol is asymptotically equal to 1/2; thus, the number of repeated runs of the protocol becomes less, making the signature length significantly smaller, with a complexity of ONt. The above schemes all use the Fiat-Shamir method to convert the identity authentication protocol into the threshold ring signature scheme, while another way to construct threshold ring signature is to combine the CFS signature algorithm with the Bresson threshold ring signature. In 2009, Dallot and Vergnaud [7]. proposed a provable security threshold ring signature scheme based on the CFS scheme. The Goppa parameterized bounded decoding problem and Goppa code distinguisher are the key to ensure the security of this scheme. Its signature length is 675N-228l, where N is the total number of ring members and l denotes how many signers there are.In some applications, it may be desirable to keep the signer’s anonymity in a ring and provide the verifier the opportunity to determine whether two signatures on the same issues were issued by the same person. This is the driving force for the development of linkable ring signature schemes [8].There are many linkable ring schemes based on the factoring and discrete logarithm problem [8–13]. Therefore, with the development of quantum computers, Shor’s algorithm poses a danger to their security [14]. In 2018, two quantum-resistant lattice-based linkable ring signatures schemes [15, 16] were proposed. The first code-based linkable ring signature scheme was presented by Branco and Mateus [17] in the same year. The complexity of this scheme is ON for both the public key size and the signature length. The public key size and signature length in [17] are slightly larger than those in [15, 16], but the private key size in [17] is much smaller than those in both schemes [15, 16].To solve the problem of the multicandidate voting problem, Yuen et al. [18] proposed a linkable threshold ring signature scheme in 2013. Specifically, the N members of the management committee can vote for multiple candidates, and each candidate can only become a candidate if he gets at least d votes. This scheme achieves a signature size of Odn. A lattice-based linkable threshold ring signature scheme is proposed in [19], which is suitable for applications that can be applied to multicategory voting systems while having a small signature length.However, the linkable threshold ring signature proposed in this paper is different from all of the above schemes. We improve on that of [17] by taking into account the following scenarios. For instance, in free group voting, there are a total of N people in the class; any t students in the class can form a group to participate in voting, but each person in the class can only vote in at most one group. For one issue, each group can only participate in at most one vote; if someone participates in more than one group to vote multiple times, the signature will be linked. At the same time, we can know how many dishonest group members there are. To solve this problem, we propose a linkable threshold ring signature scheme. In the above example, N is the number of ring members and t is the threshold value.In this paper, we give the first construction of a code-based linkable threshold ring signature scheme whose security is based on the general syndrome decoding (GSD) problem which is an NP problem. We prove that the linkable threshold ring signature scheme proposed in this paper has the security properties of existential unforgeability, anonymity, and linkability. To construct our proposal, we also give a variant of threshold GStern’s protocol, and then, we apply the Fiat-Shamir transform to it. We also prove that the threshold ring signature scheme proposed in this paper has security properties of complete, special sound, and honest-verifier-zero-knowledge (HVZK).Overall, our protocol has a signature length linear int and the best-known complexity on Ot when other number theory-based threshold ring signature schemes have complexity in ONt and those based on code theory have complexity in ON. Our protocol has a public key size linear in N, and the complexity is ON.In our proposal, signatures can be linked to each other by the same vectorri, which is the syndrome of the secret key ei and a random matrix G, where G is generated by all public keys of the members in the ring and issue.This paper is structured as follows: in the next section, the necessary preliminary knowledge needed in this paper is introduced. In Section3, we present our threshold ring signature scheme and linkable threshold ring signature scheme. Section 4 is devoted to the security analysis of our proposed schemes. Experimental result analyses including key cost, signature size, efficiency, and property comparison are shown in Section 5. Finally, the conclusion is drawn in Section 6.


## 2. Preliminaries

In this section, we give the definition of the threshold ring signature scheme and linkable ring signature scheme. Then, we introduce the hard problem in coding theory that our scheme is based on. Finally, we present the security model we adopt.


### 2.1. Threshold Ring Signature

At,N-threshold ring signature scheme [6] consists four of polynomial time algorithms, defined as follows.
(1)
T.setup(1λ): this algorithm generates system parameters with global public values by using the security parameter string 1λ as input(2)
T.KeyGen(params): this is a probabilistic polynomial-time (PPT) that accepts public parameters as input and returns a pair of secret and public keys as output sk,pk.(3)
T.Sign(params, t, pk(N), sk(t), m): this is a PPT algorithm for t users of a ring R that accepts public parameters params, a set pkN of public keys, a set of t secret keys skt, and a message m as input. On message m, the algorithm generates a t,N-threshold ring signature(4)
T.Verify(params, t, pk(N), m, σ): this is a deterministic polynomial-time (DPT) that accepts as input public parameter params, a threshold value t, a set pkN of public keys, and a pair message/signature m,σ and returns 1 if the signature on m is valid with regard to the set of public key pkN and 0 otherwise


### 2.2. Linkable Ring Signature

A linkable ring signature scheme [16] consists of four polynomial time algorithms, defined as follows.
(1)
pk,sk⟵KeyGen1λ is a PPT algorithm that takes a security parameter λ as input and produces a pair of public and secret keys pk,sk as output(2)
σ⟵Sign1λ,pkM,sk is a PPT algorithm that takes a security parameter λ, actual signers’ public key pk, the corresponding secret key sk, and a message M to be signed as inputs. It generates a signature σ(3)
b⟵Ver1λ,pkM,σ is a DPT algorithm that takes a security parameter λ, all ring members’ public key pk, a message M, and a signature σ as input. Return “1” (indicating a valid signature) and “0” (indicating an invalid signature)(4)
b⟵Link1λ,pk,M1,σ1,M2,σ2 is a DPT algorithm that accepts a list of public key pk, two messages M1 and M2, and two signatures σ1 and σ2 as input, where Ver1λ,pkM1,σ1=1 and Ver1λ,pkM2,σ2=1, respectively. For linked signatures, it returns 1; otherwise, it returns 0


### 2.3. Hard Problems

#### 2.3.1. Syndrome Decoding (SD) Problem

LetH be the parity-check matrix of a randomn,k-linear code on F2, s∈F2n−k, w is a positive integer. The problem is to find an e∈F2n satisfying wtHe≤w and s=HeT.


#### 2.3.2. General Syndrome Decoding (GSD) Problem

GivenH,G∈Z2n−k×n, s,r∈Z2n−k, and w is a positive integer. The problem is to find an e∈F2n satisfying wtHe≤w, HeT=s, GeT=r.In [20], it is pointed out that by selecting H=G and s=r as inputs, the SD problem can be simplified to the GSD problem by Karp reduction. Therefore, SD and GSD problems are equivalent. Because the SD problem is NP-complete, the GSD problem is NP-complete.


### 2.4. Security Model

The security model we adopt is based on [9, 10], which enhances the security of the linkable ring signature scheme first proposed by Liu in 2004, capturing new and practical attacking scenarios and the properties more thoroughly. In this security model, the scheme must contain these properties: existential unforgeability, anonymity, nonslanderability, and linkability.Suppose A is a PPT adversary and the security parameter isλ. Let N be the number of members in the ring; pk¯=pk1,⋯,pkN is the set of public keys of all members in the ring and L⊆pk¯. A signing oracle called Sign·,sk takes queries of the form pk¯,M and returns σ⟵Sign1λ,pk¯,M,ski, for every i between 1 and N. Co· is a corruption oracle that receives queries of the public key and outputs the responding secret key.Existential unforgeability: for each message M, if the adversary lacks a public key of this group, he is unable to forge a signature on behalf of this group. Consider the following game:Algorithm 1: Game for existential unforgeability.
GameΑunfλ,N:1.pki,ski⟵KeyGen1λi=1,⋯,N.2.L,M,σ⟵ΑSign⋅,ski,Co⋅pk¯.3.b⟵Ver1λ,L,M,σ.4.returnbwhereL,M was not asked Sign·,sk and A merely requested pk∉L from Co· [21]. The advantage that A wins the game of existentially unforgeable is
(1)AdvΑunfλ,N≔Prb=1.If we can prove thatAdvΑunfλ,N is negligible for all PPT adversaries, that is AdvΑunfλ,N≤neglλ,N, then the linkable threshold ring signature scheme is existentially unforgeable.Anonymity: an adversary cannot determine which member of the group has signed a specified message thanks to anonymity. Consider the following game:Algorithm 2: Game for anonymity.
GameΑanonλ,N:1.pki,ski⟵KeyGen1λi=0,1.2.b⟵$0,1.3.b′⟵ΑSign⋅,skb,Sign⋅,sk0,Sign⋅,sk1pk0,pk1.4.returnb′where the adversary is not permitted to askSign·,skb questions with different L, nor to ask both Sign·,skb and Sign·,sk0 or to both Sign·,skb and Sign·,sk1 with the same L. The advantage that A wins the game of anonymity is
(2)AdvΑanonλ,N≔Prb=b′−12.If we prove thatAdvΑanonλ,N≤neglλ,N, the scheme is anonymous.Nonslanderability: an adversary cannot generate a signature that is connected to another user’s signature thanks to nonslanderability, which was initially mentioned in [11] and standardized in [8]. Consider the following game:Algorithm 3: Game for nonslanderability.
GameΑnslaλ,N:1.pki,ski⟵KeyGen1λi=1,⋯,N.2.L,pk1,M1⟵ΑSign⋅,skipk¯.3.σ1⟵Sign1λ,L,M1,sk1.4.pk2,M2,σ2⟵ΑSign⋅,skipk¯,L,sk2,pk1,M1,σ1.5.b⟵Link1λ,L,M1,σ1,M2,σ2.6.returnbwherepk1, pk2∈L, pk1≠pk2 and neither L,M1, σ1 nor L,M2, σ2 was questioned nor responded to by Sign·,ski. The advantage that A wins the game of nonslanderability is
(3)AdvΑnslλ,N≔Prb=1.If we prove thatAdvΑlinkλ,L≤neglλ,N, the scheme has nonslanderability.Linkability: this property ensures that it is impossible for a user to provide two valid signatures without linking. Consider the following game:Algorithm 4: Game for linkability.
GameΑlinkλ,N:1.pki,ski⟵KeyGen1λi=1,⋯,N.2.pk⟵ΑSign⋅,skipk¯.3.L,M1,σ1,M2,σ2⟵ΑSign⋅,skipk¯,pk.4.b⟵1−Link1λ,L,M1,σ1,M2,σ2.5.returnbwhereVer1λ,L,M1,σ1=1,Ver1λ,L,M2,σ2=1 and neither L,M1, σ1 nor L,M2, σ2 were questioned or responded to by Sign·,ski. The advantage that A wins the game of linkability is
(4)AdvΑlinkλ,L≔Prb=1.If we prove thatAdvΑlinkλ,L≤neglλ,N, the scheme has linkability.


## 2.1. Threshold Ring Signature

At,N-threshold ring signature scheme [6] consists four of polynomial time algorithms, defined as follows.
(1)
T.setup(1λ): this algorithm generates system parameters with global public values by using the security parameter string 1λ as input(2)
T.KeyGen(params): this is a probabilistic polynomial-time (PPT) that accepts public parameters as input and returns a pair of secret and public keys as output sk,pk.(3)
T.Sign(params, t, pk(N), sk(t), m): this is a PPT algorithm for t users of a ring R that accepts public parameters params, a set pkN of public keys, a set of t secret keys skt, and a message m as input. On message m, the algorithm generates a t,N-threshold ring signature(4)
T.Verify(params, t, pk(N), m, σ): this is a deterministic polynomial-time (DPT) that accepts as input public parameter params, a threshold value t, a set pkN of public keys, and a pair message/signature m,σ and returns 1 if the signature on m is valid with regard to the set of public key pkN and 0 otherwise


## 2.2. Linkable Ring Signature

A linkable ring signature scheme [16] consists of four polynomial time algorithms, defined as follows.
(1)
pk,sk⟵KeyGen1λ is a PPT algorithm that takes a security parameter λ as input and produces a pair of public and secret keys pk,sk as output(2)
σ⟵Sign1λ,pkM,sk is a PPT algorithm that takes a security parameter λ, actual signers’ public key pk, the corresponding secret key sk, and a message M to be signed as inputs. It generates a signature σ(3)
b⟵Ver1λ,pkM,σ is a DPT algorithm that takes a security parameter λ, all ring members’ public key pk, a message M, and a signature σ as input. Return “1” (indicating a valid signature) and “0” (indicating an invalid signature)(4)
b⟵Link1λ,pk,M1,σ1,M2,σ2 is a DPT algorithm that accepts a list of public key pk, two messages M1 and M2, and two signatures σ1 and σ2 as input, where Ver1λ,pkM1,σ1=1 and Ver1λ,pkM2,σ2=1, respectively. For linked signatures, it returns 1; otherwise, it returns 0


## 2.3. Hard Problems

### 2.3.1. Syndrome Decoding (SD) Problem

LetH be the parity-check matrix of a randomn,k-linear code on F2, s∈F2n−k, w is a positive integer. The problem is to find an e∈F2n satisfying wtHe≤w and s=HeT.


### 2.3.2. General Syndrome Decoding (GSD) Problem

GivenH,G∈Z2n−k×n, s,r∈Z2n−k, and w is a positive integer. The problem is to find an e∈F2n satisfying wtHe≤w, HeT=s, GeT=r.In [20], it is pointed out that by selecting H=G and s=r as inputs, the SD problem can be simplified to the GSD problem by Karp reduction. Therefore, SD and GSD problems are equivalent. Because the SD problem is NP-complete, the GSD problem is NP-complete.


## 2.3.1. Syndrome Decoding (SD) Problem

LetH be the parity-check matrix of a randomn,k-linear code on F2, s∈F2n−k, w is a positive integer. The problem is to find an e∈F2n satisfying wtHe≤w and s=HeT.


## 2.3.2. General Syndrome Decoding (GSD) Problem

GivenH,G∈Z2n−k×n, s,r∈Z2n−k, and w is a positive integer. The problem is to find an e∈F2n satisfying wtHe≤w, HeT=s, GeT=r.In [20], it is pointed out that by selecting H=G and s=r as inputs, the SD problem can be simplified to the GSD problem by Karp reduction. Therefore, SD and GSD problems are equivalent. Because the SD problem is NP-complete, the GSD problem is NP-complete.


## 2.4. Security Model

The security model we adopt is based on [9, 10], which enhances the security of the linkable ring signature scheme first proposed by Liu in 2004, capturing new and practical attacking scenarios and the properties more thoroughly. In this security model, the scheme must contain these properties: existential unforgeability, anonymity, nonslanderability, and linkability.Suppose A is a PPT adversary and the security parameter isλ. Let N be the number of members in the ring; pk¯=pk1,⋯,pkN is the set of public keys of all members in the ring and L⊆pk¯. A signing oracle called Sign·,sk takes queries of the form pk¯,M and returns σ⟵Sign1λ,pk¯,M,ski, for every i between 1 and N. Co· is a corruption oracle that receives queries of the public key and outputs the responding secret key.Existential unforgeability: for each message M, if the adversary lacks a public key of this group, he is unable to forge a signature on behalf of this group. Consider the following game:Algorithm 1: Game for existential unforgeability.
GameΑunfλ,N:1.pki,ski⟵KeyGen1λi=1,⋯,N.2.L,M,σ⟵ΑSign⋅,ski,Co⋅pk¯.3.b⟵Ver1λ,L,M,σ.4.returnbwhereL,M was not asked Sign·,sk and A merely requested pk∉L from Co· [21]. The advantage that A wins the game of existentially unforgeable is
(1)AdvΑunfλ,N≔Prb=1.If we can prove thatAdvΑunfλ,N is negligible for all PPT adversaries, that is AdvΑunfλ,N≤neglλ,N, then the linkable threshold ring signature scheme is existentially unforgeable.Anonymity: an adversary cannot determine which member of the group has signed a specified message thanks to anonymity. Consider the following game:Algorithm 2: Game for anonymity.
GameΑanonλ,N:1.pki,ski⟵KeyGen1λi=0,1.2.b⟵$0,1.3.b′⟵ΑSign⋅,skb,Sign⋅,sk0,Sign⋅,sk1pk0,pk1.4.returnb′where the adversary is not permitted to askSign·,skb questions with different L, nor to ask both Sign·,skb and Sign·,sk0 or to both Sign·,skb and Sign·,sk1 with the same L. The advantage that A wins the game of anonymity is
(2)AdvΑanonλ,N≔Prb=b′−12.If we prove thatAdvΑanonλ,N≤neglλ,N, the scheme is anonymous.Nonslanderability: an adversary cannot generate a signature that is connected to another user’s signature thanks to nonslanderability, which was initially mentioned in [11] and standardized in [8]. Consider the following game:Algorithm 3: Game for nonslanderability.
GameΑnslaλ,N:1.pki,ski⟵KeyGen1λi=1,⋯,N.2.L,pk1,M1⟵ΑSign⋅,skipk¯.3.σ1⟵Sign1λ,L,M1,sk1.4.pk2,M2,σ2⟵ΑSign⋅,skipk¯,L,sk2,pk1,M1,σ1.5.b⟵Link1λ,L,M1,σ1,M2,σ2.6.returnbwherepk1, pk2∈L, pk1≠pk2 and neither L,M1, σ1 nor L,M2, σ2 was questioned nor responded to by Sign·,ski. The advantage that A wins the game of nonslanderability is
(3)AdvΑnslλ,N≔Prb=1.If we prove thatAdvΑlinkλ,L≤neglλ,N, the scheme has nonslanderability.Linkability: this property ensures that it is impossible for a user to provide two valid signatures without linking. Consider the following game:Algorithm 4: Game for linkability.
GameΑlinkλ,N:1.pki,ski⟵KeyGen1λi=1,⋯,N.2.pk⟵ΑSign⋅,skipk¯.3.L,M1,σ1,M2,σ2⟵ΑSign⋅,skipk¯,pk.4.b⟵1−Link1λ,L,M1,σ1,M2,σ2.5.returnbwhereVer1λ,L,M1,σ1=1,Ver1λ,L,M2,σ2=1 and neither L,M1, σ1 nor L,M2, σ2 were questioned or responded to by Sign·,ski. The advantage that A wins the game of linkability is
(4)AdvΑlinkλ,L≔Prb=1.If we prove thatAdvΑlinkλ,L≤neglλ,N, the scheme has linkability.


## 3. Proposed Scheme

### 3.1. Proposed Threshold GStern’s Protocol

In this section, we explain the main algorithm that composes our proposed threshold ring signature as given in Section2.1.As the go-between of both thet signers and the verifier V, the leader L is also one of the t signers. Let the i-th signer’s first, second, and third commitments be denoted as com1,i, com2,i, and com3,i, respectively. The first, second, and third commitments produced by the leader L will be denoted as COM1, COM2, and COM3, accordingly.
(1)
Commitment phase: for all 1≤i≤t, commitments com1,i, com2,i, and com3,i are computed by the leader L and other t−1 signers. As one of the t signers, L also calculates his commitments. Then, on the basis of the commitments of each signer, L utilizing them constructs the master commitments COM1, COM2, and COM3. After that, L sends COM1, COM2, and COM3 to the verifier V(2)
Challenge phase: the verifier V sends a random challenge 0, 1, or 2 to L who broadcasts it to other t−1 signers(3)
Response phase: the signers construct their responses based on the value of the given challenge and then transmit them to the leader L. After that, L delivers these responses, together with the data needed for verification, to V(4)
Verify phase: according to the challenge’s value, the verifier V validates COM1 and COM2, COM1 and COM3, or COM2 and COM3Algorithm 5: Proposed threshold GStern’s protocol.
(1)  Parameters:n, k, t∈Z(2)  Private information:ei⟵$0,1n satisfying wei=t(3)  Public information:H1, s, H2, r, where s=s1,⋯,sN, r=r1,⋯,rN satisfyingH1eiT=siT and H2eiT=riT(4)  The proverP: chooses yi⟵$, permutation δi, randomness a, b, c forcommitments.(i)  letcom1,i=hδi,HyiT,GyiT, com2,i=hδiyi, and com3,i=hδiyi+ei.(ii)  letCOM1=hcom1,1⋯com1,ta, COM2=hcom2,1⋯com2,tb, andCOM3=hcom3,1⋯com3,tc.(iii)L sends COM1, COM2, and COM3 to the verifier V(5)  The verifierV sends b⟵$0,1,2 to L, who transfers it to all the t−1 signers(6)  Thet signers(i)b=0: each signer sends RSP0,i=yi,δi to L, then L sends RSP0,1,⋯,RSP0,ta,b to V.(ii)b=1: each signer sends RSP1,i=yi+ei,δi to L, then L sends RSP1,1,⋯,RSP1,ta,c to V.(iii)b=2: each signer sends RSP2,i=δiyi,δiei to L, then L sendsRSP2,1,⋯,RSP2,t, b,c to V.(7)  The verifierV(i)b=0: the verifier uses RSP0,i to construct com1,i, com2,i, verifying thatCOM1 is equal to hcom1,1⋯com1,ta and that COM2 is equal tohcom2,1⋯com2,tb.(ii)b=1: the verifier uses RSP1,i to construct com1,i, com3,i, verifying thatCOM1 is equal to hcom1,1⋯com1,ta and that COM3 is equal tohcom3,1⋯com3,tc.(iii)b=2: the verifier uses RSP2,i to construct com2,i, com3,i, verifying thatCOM2 is equal to hcom2,1⋯com2,tb, COM3 is equal tohcom3,1⋯com3,tc and wδiei=t.


### 3.2. Proposed Linkable Ring Signature Scheme

In this section, we give the description of our new linkable threshold ring signature scheme in Algorithm6. Our scheme is improved based on the linkable ring signature scheme [17]. More precisely, our scheme is constructed by using the noninteractive protocol obtained by applying the Fiat-Shamir transform [22] to threshold GStern’s protocol.First, considering a ring withN users, use the public information pk¯=pk1,⋯,pkN and a public cryptographic hash function g to construct the matrix G. Then, generate a set of random syndromes r=r1,⋯,rN, where some ri are the vectors that have a linear relationship with the actual signer’s private information ei.Then, apply the Fiat-Shamir transform to the threshold GStern’s protocol on inputH,G,s,r, where s=s1,⋯,sN are the public information of all the ring members. From one point of view, the SD hard problem prevents the verifier from knowing which users computed r. From another point of view, with regard to the same ring, r will be a component of each signature that these users issue. If for the same issue, the intersection of the set r in two valid message signatures is not empty, the verifier links the two signatures together and outputs r. The number of signers involved in multiple signatures can be known by checking the number of identical ri.Algorithm 6: Linkable threshold ring signature scheme.
(1) Parameters:n, k, t∈N satisfying n>k, H⟵$0,1n−k×n(2) KeyGen: for each proverPi, where i denotes one of the all members in the ring, andthere areN members in ring R.(i)   randomly choosesei⟵$0,1n satisfying we=w(ii)   computessiT=HeiT(iii)   Public information ofPi: H, si, w(iv)   Private information ofPi: ei satisfying we=w and HeiT=siT(3) Sign:t signers in ring R sign the message M(i)   Compute the matrixG=gI and GeiT=riT, where I=pk¯,issuepk¯=pk1,⋯,pkN and g is a public hash function which maps pk¯ toG∈F2n−k×n.(ii)   Apply the Fiat-Shamir transform to Algorithm5 on input H,G,s,r, wheres=s1,⋯,sN, r=r1,⋯,rN.(a)  Commitment Com are calculated according to Algorithm5(b)  Simulate the verifier’s challengeb as fCom,M(c)  Calculate the corresponding responses RSP according to Algorithm5(d)  Output the transcriptT=Com,b,RSP(iii)   Output the pair of message and signatureM,σ where σ=r,Com,RSP,andr=ri1,⋯,rit, where i1,⋯,it denote the t signers.(4) Verify: the verifierV(i)   Computesb=fCom,M(ii)   ComputesG=gI(iii)   According to Algorithm5 and input H,G,s,r verifies whether T=Com,b,RSP is a valid transcript. If the signature is valid, this stage outputs “1,”otherwise, outputs “0.”(5) Link: given two signaturesM,σ and M′,σ′ where σ=r,Com,RSP, σ′=r′,Com′,RSP′, r=ri1,⋯,rit, r’=rj1,⋯,rit, where i1,⋯,it denote the t signers, j1,⋯,jt denoteothert signers, and satisfying VerM,σ=1 and VerM′,σ′=1, the verifier:(i)   Check if the intersection of the setr and r′ is empty(ii)   If the intersection is not empty, outputs “linked” and the same element fromtwo sets. Thus, it shows how many dishonest provers there are. Otherwise,accepts it and outputs “nonlinked.”


## 3.1. Proposed Threshold GStern’s Protocol

In this section, we explain the main algorithm that composes our proposed threshold ring signature as given in Section2.1.As the go-between of both thet signers and the verifier V, the leader L is also one of the t signers. Let the i-th signer’s first, second, and third commitments be denoted as com1,i, com2,i, and com3,i, respectively. The first, second, and third commitments produced by the leader L will be denoted as COM1, COM2, and COM3, accordingly.
(1)
Commitment phase: for all 1≤i≤t, commitments com1,i, com2,i, and com3,i are computed by the leader L and other t−1 signers. As one of the t signers, L also calculates his commitments. Then, on the basis of the commitments of each signer, L utilizing them constructs the master commitments COM1, COM2, and COM3. After that, L sends COM1, COM2, and COM3 to the verifier V(2)
Challenge phase: the verifier V sends a random challenge 0, 1, or 2 to L who broadcasts it to other t−1 signers(3)
Response phase: the signers construct their responses based on the value of the given challenge and then transmit them to the leader L. After that, L delivers these responses, together with the data needed for verification, to V(4)
Verify phase: according to the challenge’s value, the verifier V validates COM1 and COM2, COM1 and COM3, or COM2 and COM3Algorithm 5: Proposed threshold GStern’s protocol.
(1)  Parameters:n, k, t∈Z(2)  Private information:ei⟵$0,1n satisfying wei=t(3)  Public information:H1, s, H2, r, where s=s1,⋯,sN, r=r1,⋯,rN satisfyingH1eiT=siT and H2eiT=riT(4)  The proverP: chooses yi⟵$, permutation δi, randomness a, b, c forcommitments.(i)  letcom1,i=hδi,HyiT,GyiT, com2,i=hδiyi, and com3,i=hδiyi+ei.(ii)  letCOM1=hcom1,1⋯com1,ta, COM2=hcom2,1⋯com2,tb, andCOM3=hcom3,1⋯com3,tc.(iii)L sends COM1, COM2, and COM3 to the verifier V(5)  The verifierV sends b⟵$0,1,2 to L, who transfers it to all the t−1 signers(6)  Thet signers(i)b=0: each signer sends RSP0,i=yi,δi to L, then L sends RSP0,1,⋯,RSP0,ta,b to V.(ii)b=1: each signer sends RSP1,i=yi+ei,δi to L, then L sends RSP1,1,⋯,RSP1,ta,c to V.(iii)b=2: each signer sends RSP2,i=δiyi,δiei to L, then L sendsRSP2,1,⋯,RSP2,t, b,c to V.(7)  The verifierV(i)b=0: the verifier uses RSP0,i to construct com1,i, com2,i, verifying thatCOM1 is equal to hcom1,1⋯com1,ta and that COM2 is equal tohcom2,1⋯com2,tb.(ii)b=1: the verifier uses RSP1,i to construct com1,i, com3,i, verifying thatCOM1 is equal to hcom1,1⋯com1,ta and that COM3 is equal tohcom3,1⋯com3,tc.(iii)b=2: the verifier uses RSP2,i to construct com2,i, com3,i, verifying thatCOM2 is equal to hcom2,1⋯com2,tb, COM3 is equal tohcom3,1⋯com3,tc and wδiei=t.


## 3.2. Proposed Linkable Ring Signature Scheme

In this section, we give the description of our new linkable threshold ring signature scheme in Algorithm6. Our scheme is improved based on the linkable ring signature scheme [17]. More precisely, our scheme is constructed by using the noninteractive protocol obtained by applying the Fiat-Shamir transform [22] to threshold GStern’s protocol.First, considering a ring withN users, use the public information pk¯=pk1,⋯,pkN and a public cryptographic hash function g to construct the matrix G. Then, generate a set of random syndromes r=r1,⋯,rN, where some ri are the vectors that have a linear relationship with the actual signer’s private information ei.Then, apply the Fiat-Shamir transform to the threshold GStern’s protocol on inputH,G,s,r, where s=s1,⋯,sN are the public information of all the ring members. From one point of view, the SD hard problem prevents the verifier from knowing which users computed r. From another point of view, with regard to the same ring, r will be a component of each signature that these users issue. If for the same issue, the intersection of the set r in two valid message signatures is not empty, the verifier links the two signatures together and outputs r. The number of signers involved in multiple signatures can be known by checking the number of identical ri.Algorithm 6: Linkable threshold ring signature scheme.
(1) Parameters:n, k, t∈N satisfying n>k, H⟵$0,1n−k×n(2) KeyGen: for each proverPi, where i denotes one of the all members in the ring, andthere areN members in ring R.(i)   randomly choosesei⟵$0,1n satisfying we=w(ii)   computessiT=HeiT(iii)   Public information ofPi: H, si, w(iv)   Private information ofPi: ei satisfying we=w and HeiT=siT(3) Sign:t signers in ring R sign the message M(i)   Compute the matrixG=gI and GeiT=riT, where I=pk¯,issuepk¯=pk1,⋯,pkN and g is a public hash function which maps pk¯ toG∈F2n−k×n.(ii)   Apply the Fiat-Shamir transform to Algorithm5 on input H,G,s,r, wheres=s1,⋯,sN, r=r1,⋯,rN.(a)  Commitment Com are calculated according to Algorithm5(b)  Simulate the verifier’s challengeb as fCom,M(c)  Calculate the corresponding responses RSP according to Algorithm5(d)  Output the transcriptT=Com,b,RSP(iii)   Output the pair of message and signatureM,σ where σ=r,Com,RSP,andr=ri1,⋯,rit, where i1,⋯,it denote the t signers.(4) Verify: the verifierV(i)   Computesb=fCom,M(ii)   ComputesG=gI(iii)   According to Algorithm5 and input H,G,s,r verifies whether T=Com,b,RSP is a valid transcript. If the signature is valid, this stage outputs “1,”otherwise, outputs “0.”(5) Link: given two signaturesM,σ and M′,σ′ where σ=r,Com,RSP, σ′=r′,Com′,RSP′, r=ri1,⋯,rit, r’=rj1,⋯,rit, where i1,⋯,it denote the t signers, j1,⋯,jt denoteothert signers, and satisfying VerM,σ=1 and VerM′,σ′=1, the verifier:(i)   Check if the intersection of the setr and r′ is empty(ii)   If the intersection is not empty, outputs “linked” and the same element fromtwo sets. Thus, it shows how many dishonest provers there are. Otherwise,accepts it and outputs “nonlinked.”


## 4. Security Analysis

### 4.1. Security Analysis of Threshold Ring Signature

We prove that the protocol presented in Algorithm5 satisfies the three properties: completeness, soundness, and HVZK.Completeness: it is obvious that honest provers with access to a valid secret key can respond to any of the honest leader’s queries with the proper information, enabling him to calculate the master commitments. Meanwhile, to enable the honest verifier to confirm that these commitments are accurate, the leader is then allowed to provide the information needed. This means that the verifier will always accept the signature signed by the honest prover according to the above process. For example, for b=0, the verifier can reconstruct the master commitment COM1 and COM2 using the knowledge of comi by utilizing the knowledge of yi and δi to recover all the comi. Cases b=1 and b=2 behave similarly. Thus, the protocol has perfect completeness.Soundness: the proof of soundness for our protocol is identical to the proofs for Stern’s protocol since it is based on the generic construction in [23]. The soundness error is confined by 2/3 since the GSD problem is difficult. Meanwhile, our protocol may be thought of as a collection of t parallel GSD scheme executions. This means that the soundness error for our protocol in a single round cannot exceed 2/3. More specifically, we consider the following cases according to the various values of challenges b and b′.
(1)
Whenb=0 and b′=1, ei can be extracted from yi and yi+ei by the simulator(2)
Whenb=0 and b′=2, ei can be extracted from δi and δiei by the simulator(3)
Whenb=1 and b′=2, ei can be extracted from δi and δiei by the simulatorHVZK: the proof is analogous to the proof of HVZK for Stern’s protocol in [23]. When b=0, the simulator easily reveals yi and yi+ei. When b=1, the simulator gets xi, where HxiT=siT. When b=2, the simulator obtains a vector with weight t.


### 4.2. Security Analysis of Linkable Threshold Ring Signature

In this section, we present the analysis concerning the two aspects: correctness analysis and security analysis of the proposed scheme. We prove that the scheme has the usual properties for a linkable ring signature scheme: existential unforgeability, anonymity, nonslanderability, and linkability.


#### 4.2.1. Completeness

The completeness of our linkable threshold ring signature is easily verified. When taking an honest signature as input, the verification algorithm’s output is always correct since the underlying protocol is complete.


#### 4.2.2. Existential Unforgeability

Ref. [17] presents that existential unforgeability in the classical setting is a direct consequence of the fact that the signature is obtained by applying the Fiat-Shamir transform to a sigma protocol that is complete, special sound, and HVZK. The subprotocol called in the linkable threshold ring signature proposed in this paper, namely, Algorithm 5, has been proven to satisfy the above properties in Section 4.1, so our scheme satisfies the unforgeability.Theorem 1.
Our scheme is existentially unforgeable due to the hardness of the GSD problem.


#### 4.2.3. Anonymity

An adversary will be unable to determine which subset oft signers cooperates to sign a message due to anonymity. Supposing that we are capable of overcoming the anonymity and create an algorithm that handles the GSD problem, in order to demonstrate the anonymity of our scheme, Ref. [17] presents a method that the error vector’s w/2 nonnull coordinates must be known in advance, and the details are as follows. We are incapable of determining if the provided tuple H,s,G,r,w is a legitimate public key or is just random. With some of the secrets known, we may create another tuple H,s′,G,r′,w. There are two situations here. When H,s,G,r,w is a GSD tuple, H,s′,G,r′,w is also a GSD tuple, but when H,s,G,r,w is a random tuple, it is likewise a random tuple. Because the GSD problem is computationally difficult, knowing w/2 locations has no effect on the security proof. To keep the same level of security, we just need to raise the settings.Due to the fact that every signer only provides commitments and responses toL as in typical zero-knowledge Stern’s scheme, it is not feasible for information to be leaked between signers throughout the protocol. The outputs of all the games do not include any information on b because of the underlying protocol’s zero-knowledge feature as well as the GSD problem being challenging to solve. This means that the adversary’s likelihood of accurately estimating b is 1/2; hence, there is little chance of adversary A winning the game.Theorem 2.
Our threshold ring signature scheme is anonymous due to the hardness of the GSD problem.


#### 4.2.4. Linkability

We give the proof of public traceability from two cases:(i)
Case 1. Suppose that there is at least one rin=rjm in the set of two distinct signers, where n∈1,⋯,t, m∈1,⋯,t. Therefore, we have rinT=gIeinT=gIejmT=rjmT. In this case, the output of the proposed scheme is linked(ii)
Case 2. Suppose that rin≠rjm, for all n∈1,⋯,t, m∈1,⋯,t. Thus, we have rinT=gIeinT, rjmT=gIejmT, and rin≠rjm. Therefore, the intersection of r and r′ is empty. That means the output of this scheme is accepted and nonlinkedIt is worth noting that the same signers can sign different issues without being linked together, due to the collision resistance of hash functiong. Because the issue in I is different, so G=gI is different. Hence, even though the same signers use the same private key ei, they will have different ri, so the intersection of the two signers remains empty in the link phase.Theorem 3.
Our scheme is linkable due to the hardness of the GSD problem.


#### 4.2.5. Nonslanderability

Theorems1 and 2 have been used by the authors in [16] to demonstrate that any linkable ring signature schemes that fulfill unforgeability and linkability also satisfy the nonslanderability condition.Theorem 4.
Our scheme is nonslanderable under the SD and GSD assumptions.


## 4.1. Security Analysis of Threshold Ring Signature

We prove that the protocol presented in Algorithm5 satisfies the three properties: completeness, soundness, and HVZK.Completeness: it is obvious that honest provers with access to a valid secret key can respond to any of the honest leader’s queries with the proper information, enabling him to calculate the master commitments. Meanwhile, to enable the honest verifier to confirm that these commitments are accurate, the leader is then allowed to provide the information needed. This means that the verifier will always accept the signature signed by the honest prover according to the above process. For example, for b=0, the verifier can reconstruct the master commitment COM1 and COM2 using the knowledge of comi by utilizing the knowledge of yi and δi to recover all the comi. Cases b=1 and b=2 behave similarly. Thus, the protocol has perfect completeness.Soundness: the proof of soundness for our protocol is identical to the proofs for Stern’s protocol since it is based on the generic construction in [23]. The soundness error is confined by 2/3 since the GSD problem is difficult. Meanwhile, our protocol may be thought of as a collection of t parallel GSD scheme executions. This means that the soundness error for our protocol in a single round cannot exceed 2/3. More specifically, we consider the following cases according to the various values of challenges b and b′.
(1)
Whenb=0 and b′=1, ei can be extracted from yi and yi+ei by the simulator(2)
Whenb=0 and b′=2, ei can be extracted from δi and δiei by the simulator(3)
Whenb=1 and b′=2, ei can be extracted from δi and δiei by the simulatorHVZK: the proof is analogous to the proof of HVZK for Stern’s protocol in [23]. When b=0, the simulator easily reveals yi and yi+ei. When b=1, the simulator gets xi, where HxiT=siT. When b=2, the simulator obtains a vector with weight t.


## 4.2. Security Analysis of Linkable Threshold Ring Signature

In this section, we present the analysis concerning the two aspects: correctness analysis and security analysis of the proposed scheme. We prove that the scheme has the usual properties for a linkable ring signature scheme: existential unforgeability, anonymity, nonslanderability, and linkability.


### 4.2.1. Completeness

The completeness of our linkable threshold ring signature is easily verified. When taking an honest signature as input, the verification algorithm’s output is always correct since the underlying protocol is complete.


### 4.2.2. Existential Unforgeability

Ref. [17] presents that existential unforgeability in the classical setting is a direct consequence of the fact that the signature is obtained by applying the Fiat-Shamir transform to a sigma protocol that is complete, special sound, and HVZK. The subprotocol called in the linkable threshold ring signature proposed in this paper, namely, Algorithm 5, has been proven to satisfy the above properties in Section 4.1, so our scheme satisfies the unforgeability.Theorem 1.
Our scheme is existentially unforgeable due to the hardness of the GSD problem.


### 4.2.3. Anonymity

An adversary will be unable to determine which subset oft signers cooperates to sign a message due to anonymity. Supposing that we are capable of overcoming the anonymity and create an algorithm that handles the GSD problem, in order to demonstrate the anonymity of our scheme, Ref. [17] presents a method that the error vector’s w/2 nonnull coordinates must be known in advance, and the details are as follows. We are incapable of determining if the provided tuple H,s,G,r,w is a legitimate public key or is just random. With some of the secrets known, we may create another tuple H,s′,G,r′,w. There are two situations here. When H,s,G,r,w is a GSD tuple, H,s′,G,r′,w is also a GSD tuple, but when H,s,G,r,w is a random tuple, it is likewise a random tuple. Because the GSD problem is computationally difficult, knowing w/2 locations has no effect on the security proof. To keep the same level of security, we just need to raise the settings.Due to the fact that every signer only provides commitments and responses toL as in typical zero-knowledge Stern’s scheme, it is not feasible for information to be leaked between signers throughout the protocol. The outputs of all the games do not include any information on b because of the underlying protocol’s zero-knowledge feature as well as the GSD problem being challenging to solve. This means that the adversary’s likelihood of accurately estimating b is 1/2; hence, there is little chance of adversary A winning the game.Theorem 2.
Our threshold ring signature scheme is anonymous due to the hardness of the GSD problem.


### 4.2.4. Linkability

We give the proof of public traceability from two cases:(i)
Case 1. Suppose that there is at least one rin=rjm in the set of two distinct signers, where n∈1,⋯,t, m∈1,⋯,t. Therefore, we have rinT=gIeinT=gIejmT=rjmT. In this case, the output of the proposed scheme is linked(ii)
Case 2. Suppose that rin≠rjm, for all n∈1,⋯,t, m∈1,⋯,t. Thus, we have rinT=gIeinT, rjmT=gIejmT, and rin≠rjm. Therefore, the intersection of r and r′ is empty. That means the output of this scheme is accepted and nonlinkedIt is worth noting that the same signers can sign different issues without being linked together, due to the collision resistance of hash functiong. Because the issue in I is different, so G=gI is different. Hence, even though the same signers use the same private key ei, they will have different ri, so the intersection of the two signers remains empty in the link phase.Theorem 3.
Our scheme is linkable due to the hardness of the GSD problem.


### 4.2.5. Nonslanderability

Theorems1 and 2 have been used by the authors in [16] to demonstrate that any linkable ring signature schemes that fulfill unforgeability and linkability also satisfy the nonslanderability condition.Theorem 4.
Our scheme is nonslanderable under the SD and GSD assumptions.


## 4.2.1. Completeness

The completeness of our linkable threshold ring signature is easily verified. When taking an honest signature as input, the verification algorithm’s output is always correct since the underlying protocol is complete.


## 4.2.2. Existential Unforgeability

Ref. [17] presents that existential unforgeability in the classical setting is a direct consequence of the fact that the signature is obtained by applying the Fiat-Shamir transform to a sigma protocol that is complete, special sound, and HVZK. The subprotocol called in the linkable threshold ring signature proposed in this paper, namely, Algorithm 5, has been proven to satisfy the above properties in Section 4.1, so our scheme satisfies the unforgeability.Theorem 1.
Our scheme is existentially unforgeable due to the hardness of the GSD problem.


## 4.2.3. Anonymity

An adversary will be unable to determine which subset oft signers cooperates to sign a message due to anonymity. Supposing that we are capable of overcoming the anonymity and create an algorithm that handles the GSD problem, in order to demonstrate the anonymity of our scheme, Ref. [17] presents a method that the error vector’s w/2 nonnull coordinates must be known in advance, and the details are as follows. We are incapable of determining if the provided tuple H,s,G,r,w is a legitimate public key or is just random. With some of the secrets known, we may create another tuple H,s′,G,r′,w. There are two situations here. When H,s,G,r,w is a GSD tuple, H,s′,G,r′,w is also a GSD tuple, but when H,s,G,r,w is a random tuple, it is likewise a random tuple. Because the GSD problem is computationally difficult, knowing w/2 locations has no effect on the security proof. To keep the same level of security, we just need to raise the settings.Due to the fact that every signer only provides commitments and responses toL as in typical zero-knowledge Stern’s scheme, it is not feasible for information to be leaked between signers throughout the protocol. The outputs of all the games do not include any information on b because of the underlying protocol’s zero-knowledge feature as well as the GSD problem being challenging to solve. This means that the adversary’s likelihood of accurately estimating b is 1/2; hence, there is little chance of adversary A winning the game.Theorem 2.
Our threshold ring signature scheme is anonymous due to the hardness of the GSD problem.


## 4.2.4. Linkability

We give the proof of public traceability from two cases:(i)
Case 1. Suppose that there is at least one rin=rjm in the set of two distinct signers, where n∈1,⋯,t, m∈1,⋯,t. Therefore, we have rinT=gIeinT=gIejmT=rjmT. In this case, the output of the proposed scheme is linked(ii)
Case 2. Suppose that rin≠rjm, for all n∈1,⋯,t, m∈1,⋯,t. Thus, we have rinT=gIeinT, rjmT=gIejmT, and rin≠rjm. Therefore, the intersection of r and r′ is empty. That means the output of this scheme is accepted and nonlinkedIt is worth noting that the same signers can sign different issues without being linked together, due to the collision resistance of hash functiong. Because the issue in I is different, so G=gI is different. Hence, even though the same signers use the same private key ei, they will have different ri, so the intersection of the two signers remains empty in the link phase.Theorem 3.
Our scheme is linkable due to the hardness of the GSD problem.


## 4.2.5. Nonslanderability

Theorems1 and 2 have been used by the authors in [16] to demonstrate that any linkable ring signature schemes that fulfill unforgeability and linkability also satisfy the nonslanderability condition.Theorem 4.
Our scheme is nonslanderable under the SD and GSD assumptions.


## 5. Experimental Result Analysis

In this section, we consider the efficiency of our scheme in four aspects: public key size, secret key size, signature length, and implementation efficiency. At last, we give the comparison of safety properties.


### 5.1. Key Cost Analysis

(1)
Public key size: the public key in our scheme consists of H∈0,1n−k×n and si∈0,1n−k, where i denotes one of all the members in the ring. The public key size of our scheme is n2−nk+Nn−k bits. Hence, we achieve a size of public key in ON complexity(2)
Secret key size: the secret key of each signer is a vector ei∈0,1n, and the bit length of ei is n bits. The secret key size of our scheme is Nn bitsAccording to decoding attacks in [24], we set the parameters of our scheme under 80-bit, 128-bit, and 256-bit security as follows. For 80-bit security, we denote the scheme proposed in this paper with parameters n=1268, k=951, w=25, and p=140 as Scheme 1. For 128-bit security, we denote the scheme proposed in this paper with parameters n=2400, k=2006, w=58, and p=220 as Scheme 2. For 256-bit security, we denote the scheme proposed in this paper with parameters n=4150, k=3307, w=132, and p=440 as Scheme 3.It can be seen from Table1 that under the 80-bit security level, if there are 100 ring members, the length of the public key is 0.051 Mbytes. For fixed N=100, with 80-bit security, the public key size in [4] is 4.23 kbytes, that in [5] is 400 kbytes, and that in [6] is 8.56 kbytes. The length of the public key in this paper is shorter than that of [5] and longer than that of the scheme in [4, 6]. However, their public key lengths all have the complexity of ON.Table 1
Public key size (Mbytes).
Signature schemeN100100010000100000Scheme 10.0510.0850.4253.826Scheme 20.1170.1590.5824.809Scheme 30.4270.5171.42110.466


### 5.2. Signature Length Analysis

In our scheme, the proofσ determines the signature length, and its complexity is Ot in our scheme, where t is the threshold value. The signature size of our scheme specifically consists of the following three aspects: (i) the size of three hash values of commitments is 3λ bits, depending on the security parameter λ. (ii) The size of response is 2nt+2λ bits in each situation when b=0, b=1, or b=2. (iii) The size of the vector set r=ri1,⋯,rit is tn−k bits. The threshold GStern’s protocol needs to be repeated p times due to the cheating probability (for instance, to achieve security level with 2128, p needs to be equal to 220). In conclusion, the signature size is 3λ+tn−k+2ntp+2λp bits in our scheme. Hence, we achieve a size of signature in Ot complexity.From the above analysis, it can be found that the signature length of the proposed scheme in this paper is only related to the threshold valuet and not to the number of ring members N. Therefore, compared with other variable-length signature schemes, our scheme can achieve fixed-length signatures.The practical results presented in Table2 shows clearly the signature length of our scheme. Considering a particular example with N=100 and t=50 under the 80-bit security level, the threshold ring signature length of the scheme in [4] is 2 Mbytes, the signature length of the scheme in [5] is 2.3 Mbytes, and the signature length of our scheme is 2.1 Mbytes. These three values are in close proximity to each other. However, the signature lengths in both [4, 5] grow linearly as the number of ring members increases, while the signature length in our scheme is fixed. For example, when N=2000, the signature length in [4, 5] is obviously longer than our scheme, which is several times that of our scheme.Table 2
Signature length (Mbytes).
Signature schemet21050100Scheme 10.0870.4232.1194.239Scheme 20.2581.2596.30312.598Scheme 30.8974.38021.79943.555For fixedN=1000 and t=100 with 80-bit security, compared with the current best performing threshold ring signature scheme, the signature length of the scheme in [6] is 4.1 Mbytes and the signature length of this paper is 4.2 Mbytes, which are very close to each other, but for larger systems, i.e., with more members in the ring, the advantage of this scheme can be shown. As long as the threshold value is determined, the length of signature is fixed for any number of ring members.Compared with the lattice-based linkable threshold ring signature [19], the signature length reaches 0.28 Mbytes at the 111-bit security level with N=800 and t=2, which is longer than the signature length of our scheme using the same parameters at a higher security level. As the ring membership N increases, the signature length of [19] reaches 1.75 Mbytes when N reaches 5000, which is much larger than our scheme. It can be seen that our scheme is especially suitable for large systems, and the larger the number of ring members, the more the advantages of this scheme can be demonstrated.


### 5.3. Implementation Efficiency

The following tables show the timings we have obtained for a Python implementation. We give the implementation of our scheme on an Intel(R) Xeon(R) Gold 6148 CPU @ 2.40 GHz, running Windows 10.In the following case, the parity check matrices we used are random. The following table shows the keygen time, sign time, and verify time when the ring members are set to 100 and the number of actual provers is 2. The keygen time is consumed for the generation of the necessary public and private keys.It is vital to note that the implementation given in this paper is a proof of concept. Additionally, the experimental results in this paper are supported by the fact that the exchange of information between the leader and the provers occurs within the on the same computer or even in the same executable file. In contrast, in real life, different provers will be located on different computers, transmitting information with the leader through the network before each other, and the performance of the computers varies; in such a heterogeneous scenario, there are problems such as communication delays, so the interaction process will be dominated by the slowest provers. In order to reduce the network delay, we can make our scheme more efficient through edge computing in the wireless network [25–28].In Table3, we give some timing for the proposed linkable threshold ring signature. The saving using other matrix types such as systematic form matrices is negligible compared to the gained signature.Table 3
Execution efficiency.
SchemeKeygen time (s)Sign time (s)Verify time (s)Security levelScheme 10.03128.4210.425280Scheme 20.249164.8621.3222128Scheme 30.265996.6116.8422256


### 5.4. Comparison of Safety Features

In this section, we compare our scheme with five schemes from [4–6, 17, 19] in terms of security properties. As can be seen from Table 4, all six schemes are code-based signature schemes that are resistant to quantum attacks. In terms of linkability, only the scheme in [17, 19] and our scheme have linkability properties. In terms of threshold, all schemes except [17] have threshold properties.Table 4
Comparison of safety features.
SchemeHard problemResistant to quantum attacksLinkableThreshold[4]Minimum distance√×√[5]q-ary SD problem√×√[6]General decoding problem√×√[17]GSD problem√√×[19]Ideal lattice√√√Our schemeGSD problem√√√Both [19] and our scheme, as shown in Table 4, have both linkable and threshold features, as well as being resistant to quantum attacks. The three features listed above provide the variety of possibilities for signature application scenarios.


## 5.1. Key Cost Analysis

(1)
Public key size: the public key in our scheme consists of H∈0,1n−k×n and si∈0,1n−k, where i denotes one of all the members in the ring. The public key size of our scheme is n2−nk+Nn−k bits. Hence, we achieve a size of public key in ON complexity(2)
Secret key size: the secret key of each signer is a vector ei∈0,1n, and the bit length of ei is n bits. The secret key size of our scheme is Nn bitsAccording to decoding attacks in [24], we set the parameters of our scheme under 80-bit, 128-bit, and 256-bit security as follows. For 80-bit security, we denote the scheme proposed in this paper with parameters n=1268, k=951, w=25, and p=140 as Scheme 1. For 128-bit security, we denote the scheme proposed in this paper with parameters n=2400, k=2006, w=58, and p=220 as Scheme 2. For 256-bit security, we denote the scheme proposed in this paper with parameters n=4150, k=3307, w=132, and p=440 as Scheme 3.It can be seen from Table1 that under the 80-bit security level, if there are 100 ring members, the length of the public key is 0.051 Mbytes. For fixed N=100, with 80-bit security, the public key size in [4] is 4.23 kbytes, that in [5] is 400 kbytes, and that in [6] is 8.56 kbytes. The length of the public key in this paper is shorter than that of [5] and longer than that of the scheme in [4, 6]. However, their public key lengths all have the complexity of ON.Table 1
Public key size (Mbytes).
Signature schemeN100100010000100000Scheme 10.0510.0850.4253.826Scheme 20.1170.1590.5824.809Scheme 30.4270.5171.42110.466


## 5.2. Signature Length Analysis

In our scheme, the proofσ determines the signature length, and its complexity is Ot in our scheme, where t is the threshold value. The signature size of our scheme specifically consists of the following three aspects: (i) the size of three hash values of commitments is 3λ bits, depending on the security parameter λ. (ii) The size of response is 2nt+2λ bits in each situation when b=0, b=1, or b=2. (iii) The size of the vector set r=ri1,⋯,rit is tn−k bits. The threshold GStern’s protocol needs to be repeated p times due to the cheating probability (for instance, to achieve security level with 2128, p needs to be equal to 220). In conclusion, the signature size is 3λ+tn−k+2ntp+2λp bits in our scheme. Hence, we achieve a size of signature in Ot complexity.From the above analysis, it can be found that the signature length of the proposed scheme in this paper is only related to the threshold valuet and not to the number of ring members N. Therefore, compared with other variable-length signature schemes, our scheme can achieve fixed-length signatures.The practical results presented in Table2 shows clearly the signature length of our scheme. Considering a particular example with N=100 and t=50 under the 80-bit security level, the threshold ring signature length of the scheme in [4] is 2 Mbytes, the signature length of the scheme in [5] is 2.3 Mbytes, and the signature length of our scheme is 2.1 Mbytes. These three values are in close proximity to each other. However, the signature lengths in both [4, 5] grow linearly as the number of ring members increases, while the signature length in our scheme is fixed. For example, when N=2000, the signature length in [4, 5] is obviously longer than our scheme, which is several times that of our scheme.Table 2
Signature length (Mbytes).
Signature schemet21050100Scheme 10.0870.4232.1194.239Scheme 20.2581.2596.30312.598Scheme 30.8974.38021.79943.555For fixedN=1000 and t=100 with 80-bit security, compared with the current best performing threshold ring signature scheme, the signature length of the scheme in [6] is 4.1 Mbytes and the signature length of this paper is 4.2 Mbytes, which are very close to each other, but for larger systems, i.e., with more members in the ring, the advantage of this scheme can be shown. As long as the threshold value is determined, the length of signature is fixed for any number of ring members.Compared with the lattice-based linkable threshold ring signature [19], the signature length reaches 0.28 Mbytes at the 111-bit security level with N=800 and t=2, which is longer than the signature length of our scheme using the same parameters at a higher security level. As the ring membership N increases, the signature length of [19] reaches 1.75 Mbytes when N reaches 5000, which is much larger than our scheme. It can be seen that our scheme is especially suitable for large systems, and the larger the number of ring members, the more the advantages of this scheme can be demonstrated.


## 5.3. Implementation Efficiency

The following tables show the timings we have obtained for a Python implementation. We give the implementation of our scheme on an Intel(R) Xeon(R) Gold 6148 CPU @ 2.40 GHz, running Windows 10.In the following case, the parity check matrices we used are random. The following table shows the keygen time, sign time, and verify time when the ring members are set to 100 and the number of actual provers is 2. The keygen time is consumed for the generation of the necessary public and private keys.It is vital to note that the implementation given in this paper is a proof of concept. Additionally, the experimental results in this paper are supported by the fact that the exchange of information between the leader and the provers occurs within the on the same computer or even in the same executable file. In contrast, in real life, different provers will be located on different computers, transmitting information with the leader through the network before each other, and the performance of the computers varies; in such a heterogeneous scenario, there are problems such as communication delays, so the interaction process will be dominated by the slowest provers. In order to reduce the network delay, we can make our scheme more efficient through edge computing in the wireless network [25–28].In Table3, we give some timing for the proposed linkable threshold ring signature. The saving using other matrix types such as systematic form matrices is negligible compared to the gained signature.Table 3
Execution efficiency.
SchemeKeygen time (s)Sign time (s)Verify time (s)Security levelScheme 10.03128.4210.425280Scheme 20.249164.8621.3222128Scheme 30.265996.6116.8422256


## 5.4. Comparison of Safety Features

In this section, we compare our scheme with five schemes from [4–6, 17, 19] in terms of security properties. As can be seen from Table 4, all six schemes are code-based signature schemes that are resistant to quantum attacks. In terms of linkability, only the scheme in [17, 19] and our scheme have linkability properties. In terms of threshold, all schemes except [17] have threshold properties.Table 4
Comparison of safety features.
SchemeHard problemResistant to quantum attacksLinkableThreshold[4]Minimum distance√×√[5]q-ary SD problem√×√[6]General decoding problem√×√[17]GSD problem√√×[19]Ideal lattice√√√Our schemeGSD problem√√√Both [19] and our scheme, as shown in Table 4, have both linkable and threshold features, as well as being resistant to quantum attacks. The three features listed above provide the variety of possibilities for signature application scenarios.


## 6. Conclusions

Linkable threshold ring signature schemes have a wide range of applications, such as free group voting. In this paper, we propose a new code-based linkable threshold ring signature scheme, which is well suited for large voting systems. Our scheme is constructed by using the noninteractive protocol obtained by applying the Fiat-Shamir transform to a variety of GStern’s protocol. The signature size of our scheme is inOt, and the size of public key is ON. We also provide the existential unforgeability, anonymity, nonslanderability, and linkability of our scheme, and so, our scheme is secure in ROM due to the difficulty of the SD problem and GSD problem.



---

*Source: 3150714-2022-10-03.xml*