# A New Code-Based Traceable Ring Signature Scheme

Authors: Yanhong Qi; Li-Ping Wang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Traceable ring signatures (TRS) can reveal the identity of the signer if he signs two different messages on the same tag in the group of users. They are widely used in e-voting and cryptocurrencies such as Monero. However, there is still no secure code-based TRS scheme in the random oracle model (ROM). In this paper, we propose a code-based TRS scheme whose security is based on the hardness of the syndrome decoding problem and 2-regular null syndrome decoding problem. We show that our scheme is secure in the ROM in terms of tag-linkability, anonymity, and culpability. The signature size of our scheme is logarithmic in terms of the ring size.


---

## Body

## 1. Introduction

Ring signatures can be regarded as special group signatures, but they are differing from group signatures in that there is no group administrator in ring signatures. So, we cannot trace the real identity of the signer like group signatures. Ring signatures allow users from a group to sign messages on behalf of the group. The verifier of the ring signature can check the correctness of the signature but cannot know which person in the group is the real signer. If the same signer generates two signatures, the verifier cannot identity the signer. However, in many application scenarios [1–4], the signature represents the use by the signer of his rights, so it is important to be able to trace the signer who signs twice. For example, in a voting system for an event, users in the group can anonymously vote for the event. Dishonest users can use anonymity to vote multiple times for their own benefit. Therefore, in this case, a verifier wants to track the identities of dishonest users while protecting the privacy of honest users.In order to solve this problem, the first traceable ring signature (TRS) scheme was proposed by Fujisaki and Suzuki [5]. TRS schemes have many applications in e-voting and cryptocurrencies such as Monero. A TRS scheme can track the dishonest’s information while protecting the privacy of honest users. A TRS scheme has a tag that contains public keys of the group members and an issue. For example, an issue may be an election or a social problem. Group members can post any signed and anonymous opinions on the issue only once per tag. If a member wants to support his first opinion and submits another signed opinion, his identity will be immediately revealed. More specifically, if the signer signs the same message twice with the same tag, one will see that the two signatures are linked. If the signer signs different messages with the same tag, a TRS scheme can not only prove that the two signatures are related but also expose the identity of the signer.There are many TRS schemes [1–3, 6–8] based on factoring and discrete logarithm problems. With the emergence of large-scale quantum computers, most classic asymmetric cryptography is threatened because Shor’s algorithm can solve factoring and discrete logarithm problems in polynomial times [9]. Therefore, the postquantum secure TRS schemes have attracted much attention. Branco and Mateus proposed the first postquantum TRS scheme which is based on coding theory [10]. However, the TRS was pointed out to be unsafe due to the use of the Cramer-Damgård-Schoenmakers (CDS) framework [11] to construct OR relation in [12]. The authors in [12] also proposed a general framework and instantiated the framework with lattice-based building blocks. A hash-based one-time traceable ring signature was proposed in [13]. [14] was an extension of the work in [12]. In [14], not only lattice-based instantiation of the framework was given but also the instantiation based on symmetric-key primitives. Unlike the framework proposed in [14], we use a different way to construct the signing process and the detailed information is described in III.Code-based cryptography is a hot topic because it is thought to be secure against attacks by quantum computers. The first code-based signature scheme appeared in 2001 [15], And then, code-based signature schemes have developed greatly in the last years [16–18]. The first code-based ring signature was proposed in 2007 [19]. After that, many variations related to ring signatures have been proposed, such as linkable ring signature schemes [20], threshold ring signature schemes [21–23], and group signature schemes [24–28]. However, there is still no secure code-based TRS scheme in the random oracle model (ROM).Our Contributions. In this paper, we propose a new code-based TRS scheme in the ROM. Our scheme is an improvement on [10]. Instead of using the CDS framework in [10], we employ an accumulator [29] to construct the OR relation. Our scheme is based on the syndrome decoding (SD) problem and 2-regular null syndrome decoding (2-RNSD) problem, and we give the security analysis of the scheme in the ROM. More precisely, we construct a new protocol called Acc-GStern’s protocol by adding new relationships to the GStern’s protocol [10]. The GStern’s protocol is for a prover to prove that he has the knowledge of an error vector e for two instances of the SD problem. The Acc-GStern’s protocol is for one prover to prove that not only does he have the knowledge of a witness e for one of the several instances of the general syndrome decoding (GSD) problem but also he has values that can correctly be accumulated into the root of the code-based Merkle-tree.Consider members in the ring. For1≤i≤L, let H,si be the public keys of each user Pi, and the corresponding private key is ei. To sign a message, Pi collects the public keys of remaining L−1 members in the ring and uses them to get a hash value H˜. Then, Pi uses his secret key to get a vector ri=H˜eiT and adds a hash function on ri to get. Next, the user uses a special hash function [29] to get the leaves of the Merkle-tree and applies the Fiat-Shamir transform [30] on the Acc-GStern’s protocol to get the signature. If the signer signs two different messages in the same ring, the identity of the signer is revealed.The remainder of this paper is as follows: Section2 introduces the necessary preliminary knowledge needed in this paper. In Section 3, we present our TRS scheme. The security proof and analysis of the scheme are given in Section 4. Efficiency is shown in Section 5. Finally, the conclusion is drawn in Section 6.


## 2. Preliminaries

### 2.1. Notations

Let us start with some notations. We writeℤ2 as the set 0,1 and use n to denote the set. We use rii∈L to represent the sequence r1,r2,…,rL. Vectors and matrices will be represented in boldface lowercase letters and bold capital letters, respectively. If S is a finite set, it means that y is chosen uniformly at random from S. If A is an algorithm, we use y←Ax to show that when running with input x, the output of this algorithm is y. Let wy be the Hamming weight of the vector y. We represent the transpose of b in terms of bT. The bit-wise addition operation modulo 2 is denoted by ⊕. The function A which is negligible under the parameter n is denoted by negln, i.e., A≤1/polyn, where polyn represents any polynomial in n.


### 2.2. Hard Problems

In this section, we are going to cover some of the difficult problems used later.Problem 1.
(syndrome decoding (SD) problem).LetH∈0,1n−k×nbe a parity-check matrix of ann,krandom linear code,s∈0,1n−kbe a binary vector,t≥0be an integer, finde∈ℤ2nsuch thatwe≤t, andHeT=sT.
This problem is proven to be NP-complete in the worst case [31]. The distance between the uniform distribution over ℤ2n−k×n×ℤ2n−k and H,HeT is negligible [25].Lemma 1.
(see [10]). Letn,k′∈ℤ, andk′≤n/2. LetHbe a random matrix inℤ2k′×nandsbe a random vector inℤ2k′. The probability that one can findethat satisfiesHeT=sTis negligible.Problem 2.
(general syndrome decoding (GSD) problem).LetH,G∈0,1n−k×nbe binary matrices,s,rbe binary vectors, andt≥0be an integer. The problem is to finde∈ℤ2nsuch thatwe≤tandHeT=sT,GeT=rT.
The RSD problem is also proved to be NP-complete since the SD problem can be trivially reduced to the GSD problem [10].Lemma 2.
Letn,k′∈ℤ, andk′≤n/4. LetH,G∈0,1n−k×nbe two random matrices inℤ2k′×nands,rbe two random vectors inℤ2k′. The probability that one can findethat satisfiesHTML translation failedandGeT=rTis negligible.Definition 1.
(see [32]). A regular word is a vector of length n and weight w, and it has exactly one nonzero position in each w intervalsi−1n/w;in/wi=1,…,w. Furthermore, if the weight of each interval is two or zero, the word is called 2-regular. A 2-regular word is the sum of two regular words.Problem 3.
(2-regular null syndrome decoding (2-RNSD) problem).Letn,k,c,m∈ℤ, andm=2c·k/c. LetB∈ℤ2n×mbe a randomly matrix. The problem is to find a nonzero 2-regular wordzsuch thatB·z=0.
This problem turns out to be NP hard in the worst case [32].Definition 2.
(see [33]). For any probabilistic polynomial time adversaryA, a collision-resistant hash functionhsatisfies
Prx,x′←A1λ,h:x≠x′,hx=hx′≤ρν, where ρν is a negligible function.Definition 3 (see [14]).
A noninteractive protocol∏=Setup,P,Vfor a relationRis zero-knowledge, if there exists a pair of PPT algorithms called simulatorSO,SPs.t. for every PPT adversaryA, we have that(1)|Prb=1:pp←Setup1λ,b←AO1pp,·,·pp,−Prb=1:pp,ζ←SO1λ,b←AO2pp,ζ,·pp|≤neglλ,where O1 and O2 first validate that the input x,w∈R, else return ⊥; otherwise, O1 outputs π←Pi, and O2 outputs π←SP.


### 2.3. Merkle-Tree-Based Accumulator

In this section, we first introduce a Merkle-tree-based accumulator scheme [29] which is a building block of our traceable ring scheme. The accumulator is a one-way membership function that takes a set R as input and outputs a constant size value u. At the same time, a value d∈R has a short witness w, which makes the verifier believe that d was accumulated to u. The accumulator based on Merkle-tree structure is efficient and is also based on the following code-based hash function ℋ.Definition 4.
(see [29]). Letm=2·2c·n/c,RE:0,1n⟶0,12c·n/cbe an encoding function that mapsxtoHTML translation failed. Consider a random matrixB=B0|B1, whereB0,B1∈ℤ2n×m/2. The hash functionℋ=hB|B∈ℤ2n×mmapping0,1n×0,1nto0,1nis defined as(2)hBu0,u1=B0·REu0⊕B1·REu1.Lemma 3 (see [29]).
The above function familyℋis collision-resistant if the 2-RNSD problem is hard.
The accumulator scheme consists of four algorithms:(1)
Setupλ: the input is public parameters pp. The output is a key B for the hash function.(2)
AccuBR=d0,…,dN−1⊆0,1nN: the input is all the elements in R that treats each element as a leaf node of the Merkle-tree. The output is the root note u, which is also called the accumulated value, accumulating by R.(3)
WitGenBR,d: the input is d. If d∈R, the output is the witness w for d. Otherwise, the output is ⊥.(4)
VerifyBu,d,w: the inputs are u,d, and w. In order to obtain the accumulate value u, the verifier checks whether w is the valid hash path of u.


### 2.4. Traceable Ring Signatures

In this section, we give the definition and security model of traceable ring signatures. For simplicity of discussion, we denotepk¯=pk1,…,pkL, where pki is the public key of each user in the ring. Let issue be a string that represents the target of the signature (for example, a transaction or an election).


#### 2.4.1. Syntax

A TRS scheme contains four polynomial time algorithms defined as follows.(i)
pk,sk←KeyGen1λ: the input is the security parameter λ. KeyGen generates public and secret parameters and outputs the pair of public and secret key pk,sk.(ii)
σ←Signski,T,M: the inputs are the secret ski of the user Pi, a tag T:=pk¯,issue, and a message M∈0,1∗. The output is a signature σ on message M with the tag T. The pk¯ contains all the members in the ring and pki should be in pk¯.(iii)
b←VerT,M,σ: the inputs are the tag T=pk¯,issue, the signature σ, and the message M. The output is b=1 if accepting the signature or b=0 if not accepting it.(iv)
s←TraceT,M1,M2,σ1,σ2: the inputs are the tag T and two message/signature pairs M1,σ1, M2,σ2 that correspond to private keys ski and skj, respectively. If VerT,σ1,M1=1 and VerT,σ2,M2=1, the output is s, that is either equal to linked, accept, or pki:(3)TraceT,M1,M2,σ1,σ2≔accept,ifi≠j,linked,else ifM1=M2,pki,otherwiseM1≠M2.The correctness conditions of TRS are completeness and public traceability. The definitions are given as follows:Definition 5.
(completeness).Leti∈LandT≔pk¯,issuefor someissues. If for allpk,sk←KeyGen1λ,σ←Signski,T,Mand allM, it holds thatVerT,M,σ=1.Definition 6.
(public traceability).A TRS satisfies public traceable if the following conditions are satisfied: for allM1,M2,issue, forpk,sk←KeyGen1λ,σ1←Signski,T,M1, andσ2←Signskj,T,M2, it holds with an overwhelming probability of equation (1).


#### 2.4.2. Security Definitions

We use the security model in [5]. The security requirements of traceable ring signatures include the following three properties: tag-linkability, anonymity, and exculpability. The requirement of unforgeability (as defined in ordinary ring signatures) is not essential because the signature is unforgeable if a TRS satisfies both tag-linkability and exculpability [5].SupposeA is a probabilistic polynomial time (PPT) adversary and the security parameter is λ. Let N be the number of members in the ring; T=pk¯,issue be the tag. By negln,R, we denote a function which is negligible on the parameters n and R.(1) Tag-Linkability. Take the security parameter λ as input, output T, and N+1 valid pairs of message/signature. The adversary can get N pairs of message/signature by accessing N pairs of public and secret keys. The adversary’s advantage over the scheme is AdvAtagLink:(4)AdvAtagLinkλ,N≔PrExptA,where ExptA is(1)
T,M1,σ1,…,MN,σN←A1λ(2)
If alli∈1,…,N+1, VerT,Mi,σi=1 and i,j∈1,…,N+1,i≠j,TraceT,Mi,Mj,σi,σj=accept.If for all the PPT adversariesA, AdvAtagLinkλ,N≤neglλ,N, the scheme satisfies tag-linkability.(2) Anonymity. Let A be a PPT adversary, pk0,sk0, pk1,sk1 are two public/secret key pairs generated by KeyGen1λ. Consider the following game:(1)
pki,ski←KeyGen1λ,i∈0,1(2)
b←$0,1(3)
b′←ASignsk0,·,Signsk1,·,Signskb,·pk0,pk1(4)
Ifb=b′, output 1; otherwise, output 0.LetSignskb,· be a signing oracle. A cannot ask queries to Signskb,· with different tags nor can A ask queries with the same tag to both Signskb,· and Signsk0,· or Signskb,· and Signsk1,·. If the output of this game is 1, the adversary wins the game. The advantage that A wins the game is(5)AdvAanonλ,N≔Prb=b′−12.IfAdvAanonλ,N≤neglλ,N, the scheme is anonymous.(3) Exculpability. This requirement is presented to ensure the adversary A cannot construct two valid pairs of message/signature without knowing the secret key ski of the user Pi. The game is described as follows:(1)
pk,sk←KeyGen1λ(2)
T,M1,σ1,T,M2,σ2←ASignsk,·pk(3)
a←TraceT,M1,σ1,M2,σ2(4)
output a.In this game,VerT,M1,σ1=1 and VerT,M2,σ2=1. For the message/signature pairs that A accesses the signing oracle Signsk,· cannot link to at least one of the σ1 or σ2. This means that there is at least one message in M1 and M2 that has not been queried in the Signsk,·. The advantage that A wins the following game is(6)AdvAexculλ,N=Pra=pkIfAdvAexculλ,N≤neglλ,N, the TRS satisfies exculpability.


## 2.1. Notations

Let us start with some notations. We writeℤ2 as the set 0,1 and use n to denote the set. We use rii∈L to represent the sequence r1,r2,…,rL. Vectors and matrices will be represented in boldface lowercase letters and bold capital letters, respectively. If S is a finite set, it means that y is chosen uniformly at random from S. If A is an algorithm, we use y←Ax to show that when running with input x, the output of this algorithm is y. Let wy be the Hamming weight of the vector y. We represent the transpose of b in terms of bT. The bit-wise addition operation modulo 2 is denoted by ⊕. The function A which is negligible under the parameter n is denoted by negln, i.e., A≤1/polyn, where polyn represents any polynomial in n.


## 2.2. Hard Problems

In this section, we are going to cover some of the difficult problems used later.Problem 1.
(syndrome decoding (SD) problem).LetH∈0,1n−k×nbe a parity-check matrix of ann,krandom linear code,s∈0,1n−kbe a binary vector,t≥0be an integer, finde∈ℤ2nsuch thatwe≤t, andHeT=sT.
This problem is proven to be NP-complete in the worst case [31]. The distance between the uniform distribution over ℤ2n−k×n×ℤ2n−k and H,HeT is negligible [25].Lemma 1.
(see [10]). Letn,k′∈ℤ, andk′≤n/2. LetHbe a random matrix inℤ2k′×nandsbe a random vector inℤ2k′. The probability that one can findethat satisfiesHeT=sTis negligible.Problem 2.
(general syndrome decoding (GSD) problem).LetH,G∈0,1n−k×nbe binary matrices,s,rbe binary vectors, andt≥0be an integer. The problem is to finde∈ℤ2nsuch thatwe≤tandHeT=sT,GeT=rT.
The RSD problem is also proved to be NP-complete since the SD problem can be trivially reduced to the GSD problem [10].Lemma 2.
Letn,k′∈ℤ, andk′≤n/4. LetH,G∈0,1n−k×nbe two random matrices inℤ2k′×nands,rbe two random vectors inℤ2k′. The probability that one can findethat satisfiesHTML translation failedandGeT=rTis negligible.Definition 1.
(see [32]). A regular word is a vector of length n and weight w, and it has exactly one nonzero position in each w intervalsi−1n/w;in/wi=1,…,w. Furthermore, if the weight of each interval is two or zero, the word is called 2-regular. A 2-regular word is the sum of two regular words.Problem 3.
(2-regular null syndrome decoding (2-RNSD) problem).Letn,k,c,m∈ℤ, andm=2c·k/c. LetB∈ℤ2n×mbe a randomly matrix. The problem is to find a nonzero 2-regular wordzsuch thatB·z=0.
This problem turns out to be NP hard in the worst case [32].Definition 2.
(see [33]). For any probabilistic polynomial time adversaryA, a collision-resistant hash functionhsatisfies
Prx,x′←A1λ,h:x≠x′,hx=hx′≤ρν, where ρν is a negligible function.Definition 3 (see [14]).
A noninteractive protocol∏=Setup,P,Vfor a relationRis zero-knowledge, if there exists a pair of PPT algorithms called simulatorSO,SPs.t. for every PPT adversaryA, we have that(1)|Prb=1:pp←Setup1λ,b←AO1pp,·,·pp,−Prb=1:pp,ζ←SO1λ,b←AO2pp,ζ,·pp|≤neglλ,where O1 and O2 first validate that the input x,w∈R, else return ⊥; otherwise, O1 outputs π←Pi, and O2 outputs π←SP.


## 2.3. Merkle-Tree-Based Accumulator

In this section, we first introduce a Merkle-tree-based accumulator scheme [29] which is a building block of our traceable ring scheme. The accumulator is a one-way membership function that takes a set R as input and outputs a constant size value u. At the same time, a value d∈R has a short witness w, which makes the verifier believe that d was accumulated to u. The accumulator based on Merkle-tree structure is efficient and is also based on the following code-based hash function ℋ.Definition 4.
(see [29]). Letm=2·2c·n/c,RE:0,1n⟶0,12c·n/cbe an encoding function that mapsxtoHTML translation failed. Consider a random matrixB=B0|B1, whereB0,B1∈ℤ2n×m/2. The hash functionℋ=hB|B∈ℤ2n×mmapping0,1n×0,1nto0,1nis defined as(2)hBu0,u1=B0·REu0⊕B1·REu1.Lemma 3 (see [29]).
The above function familyℋis collision-resistant if the 2-RNSD problem is hard.
The accumulator scheme consists of four algorithms:(1)
Setupλ: the input is public parameters pp. The output is a key B for the hash function.(2)
AccuBR=d0,…,dN−1⊆0,1nN: the input is all the elements in R that treats each element as a leaf node of the Merkle-tree. The output is the root note u, which is also called the accumulated value, accumulating by R.(3)
WitGenBR,d: the input is d. If d∈R, the output is the witness w for d. Otherwise, the output is ⊥.(4)
VerifyBu,d,w: the inputs are u,d, and w. In order to obtain the accumulate value u, the verifier checks whether w is the valid hash path of u.


## 2.4. Traceable Ring Signatures

In this section, we give the definition and security model of traceable ring signatures. For simplicity of discussion, we denotepk¯=pk1,…,pkL, where pki is the public key of each user in the ring. Let issue be a string that represents the target of the signature (for example, a transaction or an election).


### 2.4.1. Syntax

A TRS scheme contains four polynomial time algorithms defined as follows.(i)
pk,sk←KeyGen1λ: the input is the security parameter λ. KeyGen generates public and secret parameters and outputs the pair of public and secret key pk,sk.(ii)
σ←Signski,T,M: the inputs are the secret ski of the user Pi, a tag T:=pk¯,issue, and a message M∈0,1∗. The output is a signature σ on message M with the tag T. The pk¯ contains all the members in the ring and pki should be in pk¯.(iii)
b←VerT,M,σ: the inputs are the tag T=pk¯,issue, the signature σ, and the message M. The output is b=1 if accepting the signature or b=0 if not accepting it.(iv)
s←TraceT,M1,M2,σ1,σ2: the inputs are the tag T and two message/signature pairs M1,σ1, M2,σ2 that correspond to private keys ski and skj, respectively. If VerT,σ1,M1=1 and VerT,σ2,M2=1, the output is s, that is either equal to linked, accept, or pki:(3)TraceT,M1,M2,σ1,σ2≔accept,ifi≠j,linked,else ifM1=M2,pki,otherwiseM1≠M2.The correctness conditions of TRS are completeness and public traceability. The definitions are given as follows:Definition 5.
(completeness).Leti∈LandT≔pk¯,issuefor someissues. If for allpk,sk←KeyGen1λ,σ←Signski,T,Mand allM, it holds thatVerT,M,σ=1.Definition 6.
(public traceability).A TRS satisfies public traceable if the following conditions are satisfied: for allM1,M2,issue, forpk,sk←KeyGen1λ,σ1←Signski,T,M1, andσ2←Signskj,T,M2, it holds with an overwhelming probability of equation (1).


### 2.4.2. Security Definitions

We use the security model in [5]. The security requirements of traceable ring signatures include the following three properties: tag-linkability, anonymity, and exculpability. The requirement of unforgeability (as defined in ordinary ring signatures) is not essential because the signature is unforgeable if a TRS satisfies both tag-linkability and exculpability [5].SupposeA is a probabilistic polynomial time (PPT) adversary and the security parameter is λ. Let N be the number of members in the ring; T=pk¯,issue be the tag. By negln,R, we denote a function which is negligible on the parameters n and R.(1) Tag-Linkability. Take the security parameter λ as input, output T, and N+1 valid pairs of message/signature. The adversary can get N pairs of message/signature by accessing N pairs of public and secret keys. The adversary’s advantage over the scheme is AdvAtagLink:(4)AdvAtagLinkλ,N≔PrExptA,where ExptA is(1)
T,M1,σ1,…,MN,σN←A1λ(2)
If alli∈1,…,N+1, VerT,Mi,σi=1 and i,j∈1,…,N+1,i≠j,TraceT,Mi,Mj,σi,σj=accept.If for all the PPT adversariesA, AdvAtagLinkλ,N≤neglλ,N, the scheme satisfies tag-linkability.(2) Anonymity. Let A be a PPT adversary, pk0,sk0, pk1,sk1 are two public/secret key pairs generated by KeyGen1λ. Consider the following game:(1)
pki,ski←KeyGen1λ,i∈0,1(2)
b←$0,1(3)
b′←ASignsk0,·,Signsk1,·,Signskb,·pk0,pk1(4)
Ifb=b′, output 1; otherwise, output 0.LetSignskb,· be a signing oracle. A cannot ask queries to Signskb,· with different tags nor can A ask queries with the same tag to both Signskb,· and Signsk0,· or Signskb,· and Signsk1,·. If the output of this game is 1, the adversary wins the game. The advantage that A wins the game is(5)AdvAanonλ,N≔Prb=b′−12.IfAdvAanonλ,N≤neglλ,N, the scheme is anonymous.(3) Exculpability. This requirement is presented to ensure the adversary A cannot construct two valid pairs of message/signature without knowing the secret key ski of the user Pi. The game is described as follows:(1)
pk,sk←KeyGen1λ(2)
T,M1,σ1,T,M2,σ2←ASignsk,·pk(3)
a←TraceT,M1,σ1,M2,σ2(4)
output a.In this game,VerT,M1,σ1=1 and VerT,M2,σ2=1. For the message/signature pairs that A accesses the signing oracle Signsk,· cannot link to at least one of the σ1 or σ2. This means that there is at least one message in M1 and M2 that has not been queried in the Signsk,·. The advantage that A wins the following game is(6)AdvAexculλ,N=Pra=pkIfAdvAexculλ,N≤neglλ,N, the TRS satisfies exculpability.


## 2.4.1. Syntax

A TRS scheme contains four polynomial time algorithms defined as follows.(i)
pk,sk←KeyGen1λ: the input is the security parameter λ. KeyGen generates public and secret parameters and outputs the pair of public and secret key pk,sk.(ii)
σ←Signski,T,M: the inputs are the secret ski of the user Pi, a tag T:=pk¯,issue, and a message M∈0,1∗. The output is a signature σ on message M with the tag T. The pk¯ contains all the members in the ring and pki should be in pk¯.(iii)
b←VerT,M,σ: the inputs are the tag T=pk¯,issue, the signature σ, and the message M. The output is b=1 if accepting the signature or b=0 if not accepting it.(iv)
s←TraceT,M1,M2,σ1,σ2: the inputs are the tag T and two message/signature pairs M1,σ1, M2,σ2 that correspond to private keys ski and skj, respectively. If VerT,σ1,M1=1 and VerT,σ2,M2=1, the output is s, that is either equal to linked, accept, or pki:(3)TraceT,M1,M2,σ1,σ2≔accept,ifi≠j,linked,else ifM1=M2,pki,otherwiseM1≠M2.The correctness conditions of TRS are completeness and public traceability. The definitions are given as follows:Definition 5.
(completeness).Leti∈LandT≔pk¯,issuefor someissues. If for allpk,sk←KeyGen1λ,σ←Signski,T,Mand allM, it holds thatVerT,M,σ=1.Definition 6.
(public traceability).A TRS satisfies public traceable if the following conditions are satisfied: for allM1,M2,issue, forpk,sk←KeyGen1λ,σ1←Signski,T,M1, andσ2←Signskj,T,M2, it holds with an overwhelming probability of equation (1).


## 2.4.2. Security Definitions

We use the security model in [5]. The security requirements of traceable ring signatures include the following three properties: tag-linkability, anonymity, and exculpability. The requirement of unforgeability (as defined in ordinary ring signatures) is not essential because the signature is unforgeable if a TRS satisfies both tag-linkability and exculpability [5].SupposeA is a probabilistic polynomial time (PPT) adversary and the security parameter is λ. Let N be the number of members in the ring; T=pk¯,issue be the tag. By negln,R, we denote a function which is negligible on the parameters n and R.(1) Tag-Linkability. Take the security parameter λ as input, output T, and N+1 valid pairs of message/signature. The adversary can get N pairs of message/signature by accessing N pairs of public and secret keys. The adversary’s advantage over the scheme is AdvAtagLink:(4)AdvAtagLinkλ,N≔PrExptA,where ExptA is(1)
T,M1,σ1,…,MN,σN←A1λ(2)
If alli∈1,…,N+1, VerT,Mi,σi=1 and i,j∈1,…,N+1,i≠j,TraceT,Mi,Mj,σi,σj=accept.If for all the PPT adversariesA, AdvAtagLinkλ,N≤neglλ,N, the scheme satisfies tag-linkability.(2) Anonymity. Let A be a PPT adversary, pk0,sk0, pk1,sk1 are two public/secret key pairs generated by KeyGen1λ. Consider the following game:(1)
pki,ski←KeyGen1λ,i∈0,1(2)
b←$0,1(3)
b′←ASignsk0,·,Signsk1,·,Signskb,·pk0,pk1(4)
Ifb=b′, output 1; otherwise, output 0.LetSignskb,· be a signing oracle. A cannot ask queries to Signskb,· with different tags nor can A ask queries with the same tag to both Signskb,· and Signsk0,· or Signskb,· and Signsk1,·. If the output of this game is 1, the adversary wins the game. The advantage that A wins the game is(5)AdvAanonλ,N≔Prb=b′−12.IfAdvAanonλ,N≤neglλ,N, the scheme is anonymous.(3) Exculpability. This requirement is presented to ensure the adversary A cannot construct two valid pairs of message/signature without knowing the secret key ski of the user Pi. The game is described as follows:(1)
pk,sk←KeyGen1λ(2)
T,M1,σ1,T,M2,σ2←ASignsk,·pk(3)
a←TraceT,M1,σ1,M2,σ2(4)
output a.In this game,VerT,M1,σ1=1 and VerT,M2,σ2=1. For the message/signature pairs that A accesses the signing oracle Signsk,· cannot link to at least one of the σ1 or σ2. This means that there is at least one message in M1 and M2 that has not been queried in the Signsk,·. The advantage that A wins the following game is(6)AdvAexculλ,N=Pra=pkIfAdvAexculλ,N≤neglλ,N, the TRS satisfies exculpability.


## 3. A Code-Based TRS Scheme

### 3.1. A Proof of Knowledge Protocol

We use a so-called GStern’s protocol in [10] to construct our TRS scheme. Given H,G and s,r in the GSD problem, the prover Pi wants the verifier V to confirm that he has a small weight vector e such that HeT=sT and GeT=rT. In other words, the protocol is a proof of knowledge protocol for the GSD problem. To be self-contained, we give the detailed description in Algorithm 1, in which h denotes a cryptographic hash function.Algorithm 1: GStern’s protocol.
(1)
Parameters:n,k,t(2)
Private information:e∈ℤ2n and we=t.(3)
Public information:H,G,s,r, where HeT=sT andGeT=rT.(4)
The proverPi:(i)
choosesy⟵$ℤ2n and a permutation δ.(ii)
setsc1=hδ,HyT,GyT, c2=hδy,(iii)
andc3=hδy+e.(iv)
sendsc1, c2, and c3.(5)
The verifierV: - sends b⟵$0,1,2.(6)
The proverPi:(i)
ifb=0, sets f≔y,δ.(ii)
ifb=1, sets f≔y+e,δ.(iii)
ifb=2, sets f≔δy,δe.(iv)
sendsf.(7)
The verifierV:(i)
ifb=0, accepts if hδ,HyT,GyT=c1 and hδy=c2.(ii)
ifb=1, accepts if hδ,Hy+eT+sT,Gy+eT+rT=c1 and hδy+e=c3.(iv)
ifb=2, accepts if hδy=c2,hδy+δe=c3, and wδe=t.The GStern’s protocol satisfies the following three natures: completeness, special soundness, and honest-verifier zero-knowledge (HVZK) [10]. To construct our TRS scheme, we apply the code-based Merkle-tree accumulator [29] to GStern’s protocol. The statistical zero-knowledge argument of the accumulator allows the prover Pi to convince the verifier V, under zero-knowledge conditions, that P knows a value correctly accumulated into the code-based Merkle-tree root described above. Let the uniformly random matrix B∈ℤ2n×m and the accumulated value u be the input. The goal of Pi is to convince V that he has a value d and a valid witness w. The relationship with the accumulator is Racc=B,u∈ℤ2n×m×0,1n,d∈0,1n,w∈0,1l×0,1nl:VerifyBu,d,w=1. The authors of [29] gave specific techniques how to reduce the relationship Racc to the abstract relationship Rabstract=M,v,w∈ℤ2K×L×ℤ2K×VALID:M·w=v, where M,w,v are obtained by doing some transforms to B,u,d. In other words, if we want to construct relation Racc, we only need to construct relation Rabstract. We summarize the above method into the new protocol Acc-GStern’s protocol described in Algorithm 2. The COM denotes a commitment scheme and S is a finite set, where each ϕ∈S is associated with a permutation Γϕ of L elements. In addition, VALID is a subset of 0,1L.Algorithm 2: Acc-GStern’s protocol.
(1)
Parameters:n,k,t,K,L∈ℕ,L≥K.(2)
Private information:e,w.(3)
Public information:(i)
H,s,G,r, where HeT=sT and GeT=rT.(ii)
M,v, where M·w=v.(4)
The proverP:- chooses y⟵$ℤ2n, rw⟵$ℤ2L, a permutation δ, a permutation ϕ⟵$S, randomness ρ1, ρ2, ρ3 for COM.(i)
setsc1=hδ,HyT,GyT, c2=hδy, and c3=hδy+e.(ii)
setsC1=COMϕ,M·rw;ρ1, C2=COMΓϕrw;ρ2. and C3=COMΓϕw⊕rw;ρ3.(iii)
sendsc1, c2, c3, C1, C2, and C3.(5)
The verifierV:(i)
sendsb←$0,1,2.(6)
The proverP:(i)
ifb=0, computes tw=Γϕw,tr=Γϕrw, sets f≔y,δ,tw,tr,ρ2,ρ3.(ii)
ifb=1, computes w2=w⊕rw,ϕ2=ϕ, sets f≔y+e,δ,ϕ2,w2,ρ1,ρ3.(iii)
ifb=2, computes ϕ3=ϕ,w3=rw, sets f≔δy,δe,ϕ3,w3,ρ1,ρ2.(iv)
sendsf.(7)
The verifierV:(i)
ifb=0, accepts if hδ,HyT,GyT=c1,hδy=c2,tw∈VALID,C2=COMtr;ρ2,C3=COMtw⊕tr;ρ3.(ii)
ifb=1, accepts if hδ,Hy+eT+sT,Gy+eT+rT=c1,hδy+e=c3,C1=COMϕ2,M·w2⊕v;ρ1andC3=COMΓϕ2w2;ρ3.(iii)
ifb=2, accepts if hδy=c2,hδy+δe=c3, wδe=t,C1=COMϕ3,M·w3;ρ1andC2=COMΓϕ3w3;ρ2.Lemma 4.
The protocol presented inAlgorithm 2is complete, special sound, and HVZK.Proof.
Our new protocol is a combination of GStern’s protocol and the accumulator protocol. If an honest prover follows the protocol, then he always gets accepted by the verifier. Thus, the protocol has perfect completeness. If there is a simulator who extracts a valid witness from two valid transcriptscom,ch,resp and com,ch′,resp′ of Acc-GStern’s protocol with ch≠ch′, where com, chch′ and respresp′ are commitments, challenges, and responses, respectively, he can extract a valid witness. We consider the following cases:(1)
Whench=0 and ch′=1, the simulator can extract e from y and y+e. For ϕ2=ϕ, the simulator can extract w from Γϕw.(2)
Whench=0 and ch′=2, the simulator can extract e from δ and δe. For ϕ3=ϕ, the simulator can extract w from Γϕw and ϕ.(3)
Whench=1 and ch′=2, the simulator can extract e from δ and δe and the simulator can extract w from rw and w⊕rw.
Finally, we prove HVZK of the protocol. Whenb=0, the simulator easily reveals y, y+e, Γϕw, and Γϕrw. When b=1, the simulator gets x, where HxT=sT and reveals a vector y, where M·y⊕rw⊕v=M·rw. When b=2, the simulator obtains a vector with weight t and a vector of length L.


### 3.2. Description of the Scheme

In this section, we give the description of our new TRS scheme inAlgorithm 3. Generally speaking, the scheme is constructed by using the noninteractive protocol ∏≔Setup,P,V which is obtained by combining Acc-GStern’s protocol with Fiat-Shamir transform [30].First, we use the public informationT and a collision-resistant hash function h1 to construct the matrix H˜. Then, we construct a set of random syndromes r1,r2, …, rL, one of which, i.e., some ri, is a vector associated with the secret key of the actual signer. When the same signer signs two different messages with the same tag, the vector ri will be the same and so we can identity the signer. We also use a collision-resistant hash function g to generate the other rj, where j≠i, to prevent the signer from cheating.LetP1,P2,…,PL be the members of the ring, and pk¯=pk1,pk2,…,pkL be the public keys of the members. The tag is T=issue,pk¯. Let issue be a string of signed targets (for example, an election or a transaction). Let h1:ℤ2∗⟶ℤ2n−k×n,g:ℤ2∗⟶ℤnn−k and h2 be three different collision-resistant hash functions. The hash function h2 is the special function used in the accumulator as we defined in Definition 4. In addition, gix is the function g applied i times on input x.Algorithm 3: Our TRS scheme.
(1)
Parameters:n,t,c,r,k′∈ℕ,m=2·2c·k′/c,k=3n/4,H←$0,1n−k×n,B←$ℤ2r×m.(2)
KeyGen: For each user Pi,i∈L(i)
randomly choosesei∈0,1n such that wei=t.(ii)
computessiT=HeiT.(iii)
theprivatekey:ei.(iv)
thepublickey:H,B,si.(3)
Sign: To generate a signature on message HTML translation failed, the user Pi(i)
computesH˜=h1T and H˜eiT=riT.(ii)
setsA0=ri+gM+⋯+giM.(iii)
computesrj=A0+gM+⋯+gjM, for j∈L,j≠i.(iv)
computesdi=h2si,ri, for all i∈L, and defines R=dii∈L.(v)
computesu=AccuBR and wi=WitGenBR,di.(vi)
letX≔H,H˜,si,ri,B,di,u be the public input of the protocol ∏, and let W≔wi,ei be the secret inputs. Then, the user runs P to generate a noninteractive proof ν.(vii)
outputs the signatureσ=ν,A0.(4)
Verify: To verify the signature σ on message M, the verifier(i)
computesri=A0+gM+g2M…+giM, for all i∈L.(ii)
computesdi=h2si,ri, for all i∈L, and defines R=diL.(iii)
computesu=AccuBR.(iv)
letX≔H,H˜,si,ri,B,di,u be the public input of the protocol ∏. Then, the verifier runs V to get μ.(v)
ifμ=1, outputs 1. Otherwise, outputs 0.(5)
Trace: When the verifier is given two signatures T,M,σ and T,M′,σ′, where σ=ν,A0 and σ′=ν′,A0′, the verifier(i)
ifVerifyT,M,σ=1 and VerifyT,M′,σ′=1, continue.(ii)
computesrj=A0+gM+⋯+gjM and rj′=A0′+gM′+⋯+gjM′ for all j∈L.(iii)
ifrj=rj′ for all j∈L, outputs linked.(iv)
else if only one indexj∈L makes rj=rj′, outputs pki.(v)
otherwise, outputsaccept.


## 3.1. A Proof of Knowledge Protocol

We use a so-called GStern’s protocol in [10] to construct our TRS scheme. Given H,G and s,r in the GSD problem, the prover Pi wants the verifier V to confirm that he has a small weight vector e such that HeT=sT and GeT=rT. In other words, the protocol is a proof of knowledge protocol for the GSD problem. To be self-contained, we give the detailed description in Algorithm 1, in which h denotes a cryptographic hash function.Algorithm 1: GStern’s protocol.
(1)
Parameters:n,k,t(2)
Private information:e∈ℤ2n and we=t.(3)
Public information:H,G,s,r, where HeT=sT andGeT=rT.(4)
The proverPi:(i)
choosesy⟵$ℤ2n and a permutation δ.(ii)
setsc1=hδ,HyT,GyT, c2=hδy,(iii)
andc3=hδy+e.(iv)
sendsc1, c2, and c3.(5)
The verifierV: - sends b⟵$0,1,2.(6)
The proverPi:(i)
ifb=0, sets f≔y,δ.(ii)
ifb=1, sets f≔y+e,δ.(iii)
ifb=2, sets f≔δy,δe.(iv)
sendsf.(7)
The verifierV:(i)
ifb=0, accepts if hδ,HyT,GyT=c1 and hδy=c2.(ii)
ifb=1, accepts if hδ,Hy+eT+sT,Gy+eT+rT=c1 and hδy+e=c3.(iv)
ifb=2, accepts if hδy=c2,hδy+δe=c3, and wδe=t.The GStern’s protocol satisfies the following three natures: completeness, special soundness, and honest-verifier zero-knowledge (HVZK) [10]. To construct our TRS scheme, we apply the code-based Merkle-tree accumulator [29] to GStern’s protocol. The statistical zero-knowledge argument of the accumulator allows the prover Pi to convince the verifier V, under zero-knowledge conditions, that P knows a value correctly accumulated into the code-based Merkle-tree root described above. Let the uniformly random matrix B∈ℤ2n×m and the accumulated value u be the input. The goal of Pi is to convince V that he has a value d and a valid witness w. The relationship with the accumulator is Racc=B,u∈ℤ2n×m×0,1n,d∈0,1n,w∈0,1l×0,1nl:VerifyBu,d,w=1. The authors of [29] gave specific techniques how to reduce the relationship Racc to the abstract relationship Rabstract=M,v,w∈ℤ2K×L×ℤ2K×VALID:M·w=v, where M,w,v are obtained by doing some transforms to B,u,d. In other words, if we want to construct relation Racc, we only need to construct relation Rabstract. We summarize the above method into the new protocol Acc-GStern’s protocol described in Algorithm 2. The COM denotes a commitment scheme and S is a finite set, where each ϕ∈S is associated with a permutation Γϕ of L elements. In addition, VALID is a subset of 0,1L.Algorithm 2: Acc-GStern’s protocol.
(1)
Parameters:n,k,t,K,L∈ℕ,L≥K.(2)
Private information:e,w.(3)
Public information:(i)
H,s,G,r, where HeT=sT and GeT=rT.(ii)
M,v, where M·w=v.(4)
The proverP:- chooses y⟵$ℤ2n, rw⟵$ℤ2L, a permutation δ, a permutation ϕ⟵$S, randomness ρ1, ρ2, ρ3 for COM.(i)
setsc1=hδ,HyT,GyT, c2=hδy, and c3=hδy+e.(ii)
setsC1=COMϕ,M·rw;ρ1, C2=COMΓϕrw;ρ2. and C3=COMΓϕw⊕rw;ρ3.(iii)
sendsc1, c2, c3, C1, C2, and C3.(5)
The verifierV:(i)
sendsb←$0,1,2.(6)
The proverP:(i)
ifb=0, computes tw=Γϕw,tr=Γϕrw, sets f≔y,δ,tw,tr,ρ2,ρ3.(ii)
ifb=1, computes w2=w⊕rw,ϕ2=ϕ, sets f≔y+e,δ,ϕ2,w2,ρ1,ρ3.(iii)
ifb=2, computes ϕ3=ϕ,w3=rw, sets f≔δy,δe,ϕ3,w3,ρ1,ρ2.(iv)
sendsf.(7)
The verifierV:(i)
ifb=0, accepts if hδ,HyT,GyT=c1,hδy=c2,tw∈VALID,C2=COMtr;ρ2,C3=COMtw⊕tr;ρ3.(ii)
ifb=1, accepts if hδ,Hy+eT+sT,Gy+eT+rT=c1,hδy+e=c3,C1=COMϕ2,M·w2⊕v;ρ1andC3=COMΓϕ2w2;ρ3.(iii)
ifb=2, accepts if hδy=c2,hδy+δe=c3, wδe=t,C1=COMϕ3,M·w3;ρ1andC2=COMΓϕ3w3;ρ2.Lemma 4.
The protocol presented inAlgorithm 2is complete, special sound, and HVZK.Proof.
Our new protocol is a combination of GStern’s protocol and the accumulator protocol. If an honest prover follows the protocol, then he always gets accepted by the verifier. Thus, the protocol has perfect completeness. If there is a simulator who extracts a valid witness from two valid transcriptscom,ch,resp and com,ch′,resp′ of Acc-GStern’s protocol with ch≠ch′, where com, chch′ and respresp′ are commitments, challenges, and responses, respectively, he can extract a valid witness. We consider the following cases:(1)
Whench=0 and ch′=1, the simulator can extract e from y and y+e. For ϕ2=ϕ, the simulator can extract w from Γϕw.(2)
Whench=0 and ch′=2, the simulator can extract e from δ and δe. For ϕ3=ϕ, the simulator can extract w from Γϕw and ϕ.(3)
Whench=1 and ch′=2, the simulator can extract e from δ and δe and the simulator can extract w from rw and w⊕rw.
Finally, we prove HVZK of the protocol. Whenb=0, the simulator easily reveals y, y+e, Γϕw, and Γϕrw. When b=1, the simulator gets x, where HxT=sT and reveals a vector y, where M·y⊕rw⊕v=M·rw. When b=2, the simulator obtains a vector with weight t and a vector of length L.


## 3.2. Description of the Scheme

In this section, we give the description of our new TRS scheme inAlgorithm 3. Generally speaking, the scheme is constructed by using the noninteractive protocol ∏≔Setup,P,V which is obtained by combining Acc-GStern’s protocol with Fiat-Shamir transform [30].First, we use the public informationT and a collision-resistant hash function h1 to construct the matrix H˜. Then, we construct a set of random syndromes r1,r2, …, rL, one of which, i.e., some ri, is a vector associated with the secret key of the actual signer. When the same signer signs two different messages with the same tag, the vector ri will be the same and so we can identity the signer. We also use a collision-resistant hash function g to generate the other rj, where j≠i, to prevent the signer from cheating.LetP1,P2,…,PL be the members of the ring, and pk¯=pk1,pk2,…,pkL be the public keys of the members. The tag is T=issue,pk¯. Let issue be a string of signed targets (for example, an election or a transaction). Let h1:ℤ2∗⟶ℤ2n−k×n,g:ℤ2∗⟶ℤnn−k and h2 be three different collision-resistant hash functions. The hash function h2 is the special function used in the accumulator as we defined in Definition 4. In addition, gix is the function g applied i times on input x.Algorithm 3: Our TRS scheme.
(1)
Parameters:n,t,c,r,k′∈ℕ,m=2·2c·k′/c,k=3n/4,H←$0,1n−k×n,B←$ℤ2r×m.(2)
KeyGen: For each user Pi,i∈L(i)
randomly choosesei∈0,1n such that wei=t.(ii)
computessiT=HeiT.(iii)
theprivatekey:ei.(iv)
thepublickey:H,B,si.(3)
Sign: To generate a signature on message HTML translation failed, the user Pi(i)
computesH˜=h1T and H˜eiT=riT.(ii)
setsA0=ri+gM+⋯+giM.(iii)
computesrj=A0+gM+⋯+gjM, for j∈L,j≠i.(iv)
computesdi=h2si,ri, for all i∈L, and defines R=dii∈L.(v)
computesu=AccuBR and wi=WitGenBR,di.(vi)
letX≔H,H˜,si,ri,B,di,u be the public input of the protocol ∏, and let W≔wi,ei be the secret inputs. Then, the user runs P to generate a noninteractive proof ν.(vii)
outputs the signatureσ=ν,A0.(4)
Verify: To verify the signature σ on message M, the verifier(i)
computesri=A0+gM+g2M…+giM, for all i∈L.(ii)
computesdi=h2si,ri, for all i∈L, and defines R=diL.(iii)
computesu=AccuBR.(iv)
letX≔H,H˜,si,ri,B,di,u be the public input of the protocol ∏. Then, the verifier runs V to get μ.(v)
ifμ=1, outputs 1. Otherwise, outputs 0.(5)
Trace: When the verifier is given two signatures T,M,σ and T,M′,σ′, where σ=ν,A0 and σ′=ν′,A0′, the verifier(i)
ifVerifyT,M,σ=1 and VerifyT,M′,σ′=1, continue.(ii)
computesrj=A0+gM+⋯+gjM and rj′=A0′+gM′+⋯+gjM′ for all j∈L.(iii)
ifrj=rj′ for all j∈L, outputs linked.(iv)
else if only one indexj∈L makes rj=rj′, outputs pki.(v)
otherwise, outputsaccept.


## 4. Security and Analysis

In this section, we present the analysis of our TRS scheme from two aspects: correctness analysis and security analysis.


### 4.1. Correctness Analysis

If a TRS scheme satisfies completeness and public traceability which are given in Definition5 and Definition 6, respectively, we say that the TRS scheme is correct.


#### 4.1.1. Completeness

The completeness of our TRS is easily verified. Sinceh and g are collision-resistant hash functions, and A0 is generated by the tag and the secret key ei, the signer can always generate all ri and di for all i∈L, just like in the signing algorithm. The verifier can recover all ri from A0 and also recover all di. Due to the completeness of the underlying protocol, the output of the verification algorithm is always 1 when the input of the verification algorithm is the honest signature ν.


#### 4.1.2. Public Traceability

Next, we give the proof of public traceability from three cases:(i)
Case 1. Suppose thatM=M′, i=i′. Therefore, we have riT=h1TeiT=h1Tei'T=ri'T, and we get rj=rj′ for all j∈L. In this case, the output of Trace is always linked.(ii)
Case 2. Suppose thatM≠M′,i=i′. So, we have riT=h1TeiT=h1Tei'T=ri'T. However, due to the collision resistance of the hash function g, we have rj≠rj′, for j∈L,j≠i with overwhelming probability. Therefore, only ri=ri′ in the two sequences rjj∈L and rj′j∈L. In this case, the output of Trace is always pki.(iii)
Case 3. Suppose thati≠i′ and M=M′. Thus, we have riT=h1TeiT, h1Tei'T=ri'T, and ri≠ri′. Then, due to the hash function, we have rj≠rj′ for all j∈L with overwhelming probability. If i≠i′ and M≠M′, we obtain ri≠ri′. If the output of the algorithm Trace is not accept, there must be some j≠i,j∈L, satisfying rj=rj′. However, we have rj=A0+gM+⋯+gjM and rj′=A0′+gM′+⋯+gjM′. Due to the collision resistance of hash functions and the difficulty of the GSD problem, the probability of the existence of rj and rj′ is negligible. Therefore, the output of Trace is accept with overwhelming probability.


### 4.2. Security Analysis

We use the security definition of TRS in [5], which formalized security requirements called anonymity, tag-linkability, and exculpability.Theorem 1.
Our scheme is secure in the random oracle model, i.e., satisfying anonymity, tag-linkability, and exculpability.We prove Theorem1 from the following three aspects: proof for anonymity, proof for tag-linkability, and proof for exculpability.


#### 4.2.1. Proof for Anonymity

To show that our scheme satisfies anonymity, we define a PPT adversaryA, a challenger C, and a series of games Gi, i=0,1,2,3,4. There are three signing oracles: Signsk0,Signsk1,Signb. The advantage of the adversary A in Gi is denoted by AdvA,Gianon.G0: this game is just like the game defined in (2), in which b=0. The adversary A can access three oracles. The challenger C honestly runs the Signski oracle with corresponding secret keys to reply to A’s queries to these there oracles.G1: let SP,SO be the simulators of the protocol ∏. The challenger C runs SO to simulate the public parameters, instead of running Setup of the protocol ∏. When the adversary A makes queries to Signskb, the challenger C runs SP to answer the query.Due to Definition3, we have(7)AdvA,G0anonλ≈AdvA,G1anonλ.G2: the difference between G2 and G1 is that the challenger C creates an empty table δ. We assume that the sequence r1i,r2i,…,rLi is computed by the user Pi, and i is the position of pki in T. The adversary A gets access to Signskb and the query is T,M.The challenger C does not use h1TebT to get rbb. The challenger C checks whether there is a tuple T,M,r∗b in δ, where r∗b is the vector in δ together with T,M. If the tuple exists, then C uses r∗b and runs the simulator SP to generate the signature. Otherwise, the challenger C randomly chooses a vector rbb←$ℤ2n−k, sets r∗b=rbb, and adds T,M,rbb to δ. Then, the challenger C generates the signature using rbb.Due to the GSD problem, the adversary cannot calculatee from rbb and the public parameters. So, A cannot distinguish G1 and G2:(8)AdvA,G1anonλ≈AdvA,G2anonλ.G3: the difference between G3 and G2 is that the challenger C uses sk1 to generate rj and answers the query to Signskb. G4: the difference between G0 and G4 is the value of b. G4 defines b=1.Due to the zero-knowledge property of the underlying protocol and the hardness of the GSD problem, the outputs of all the above games contain nothing aboutb. Therefore, the adversary can guess the right b with probability 1/2 and the advantage that the adversary A wins the game is negligible.


#### 4.2.2. Proof for Tag-Linkability

We assume that the PPT adversary isA and the sequence rii∈L is contained in the signature which can be reconstructed from T,Mi,νi,A0. The L+1 message/signature pairs M1,σ1,…,ML+1,σL+1 with tag T are generated by the adversary A. Suppose that A wins the tag-linkability game. Thus, we have aVerifyσi,Mi,T=1,∀i∈L+1; and bTraceT,Mi,σi,Mj,σj=accept,∀i,j∈L+1,i≠j.LetIreal and ISO be the sets of all the parameters honestly generated in our construction and all the parameters generated by the simulator SO, respectively. Due to the zero-knowledge property of the protocol, A cannot distinguish Ireal and ISo. Therefore, there is an extractor that can extract a witness w=i,ei for each Mi,σi. There is at most only one witness with overwhelming probability because of the hardness of the GSD problem, and correspondingly, siT=HeiT and riT=h1TeiT,i∈L+1. Since T only contains L public keys, there must exist si=sj,i≠j in the sequence pkii∈L+1. Since all public keys in T are distinct, we have ei=ej. Finally, we get riT=h1TeiT=h1TejT=rjT, which means that two signatures σi and σj cannot be accepted by Trace. However, this contradicts our previous assumptions.


#### 4.2.3. Proof for Exculpability

Suppose thatA is a PPT adversary. We define the following games Gi,i=0,1.G0: this is the real exculpability game. In this game, the challenger C runs KeyGen to generate pkj,skj, where j is the position of pkj in T. C runs Signskj to reply to A’s queries to Signskj.G1: the challenger C runs the simulator of the protocol ∏ to generate the public parameters and randomly chooses si←$ℤ2n−k. C creates an empty table δ to record each query. The challenger C receives a query T,M to Signskj and the secret key skj corresponds to the public key pkj in T, where HTML translation failed is the position of pkj in T. However, C does not compute rjj in terms of h1TejT. If T,M,r∗j is not in the table δ, where r∗j is the vector in δ together with T,M, he randomly chooses a vector r∗j←$ℤ2n−k and adds T,M,r∗j to the table δ and generates the signature with r∗j. Otherwise, C sets rjj as r∗j and uses the simulator SP to generate the signature.Due to the zero-knowledge property of the underlying protocol and the hardness of the GSD problem, the advantage thatA distinguishes G0 and G1 is(9)AdvA,G0exculλ≈AdvA,G1exculλ.Then, we show that a successful attack is impossible inG1. If A can output two valid pairs T,M,σ and T,M′,σ′, the two valid pairs can satisfy:(1)
VerifyT,M,σ=1 and VerifyT,M′,σ′=1,(2)
TraceT,M,σ,M′,σ′=pki, where i is the position of pki in T.We consider the following two cases:(i)
Case 1. Suppose that one of those two pairs can be linked with the tableδ and the pair is T,M′,σ′=ν′,A0′. Therefore, there is a pair T,M∗,σ∗=ν∗,A0 in δ that can be linked with T,M′,σ′=ν′,A0′ where M∗ and σ∗ are the vectors in δ in the target pair and ν∗,A0 are the vectors corresponding to σ∗. We can get a witness w=i′,ei′ from the extractor of the protocol ∏. In this way, the elements in the pair should satisfy si′T=Hei′T, ri′T=h1Tei′T and rj′=A0′+gM′+⋯+gjM′ for all j∈L,j≠i, and due to that the two pairs are linked, s∗=si′ and rj∗=rj′, for all j∈L. However, s∗ is generated by the simulator of the protocol ∏ and the vectors rj∗, j∈L are randomly chosen in ℤ2n−k in G1. Considering the hardness of the GSD problem, the adversary A cannot generate the valid e′ and r′.(ii)
Case 2. Suppose that neither of the two pairs can be associated with the tableδ. So, we have rj=rj′, which means that A0+gM+⋯+gjM=A0′+gM′+⋯+gjM′, for all j∈L. We can also extract the witness i,ei and i′,ei′ from ν and ν′, respectively. We have h1TeiT=riT and h1Tei′T=ri′T, which holds that h1TeiT=h1Tei′T. If i=i′, the Trace will output si. However, ri is chosen randomly in ℤ2n−k in G1, and so A cannot construct a vector ei which satisfies HeiT=siT and h1TeiT=riT. In this condition, we have i≠i′. Due to the hardness of the GSD problem, the probability that the adversary A constructs the valid ei,ei′,ri,ri′ is negligible. Therefore, the adversary A cannot have a successful attack.


## 4.1. Correctness Analysis

If a TRS scheme satisfies completeness and public traceability which are given in Definition5 and Definition 6, respectively, we say that the TRS scheme is correct.


### 4.1.1. Completeness

The completeness of our TRS is easily verified. Sinceh and g are collision-resistant hash functions, and A0 is generated by the tag and the secret key ei, the signer can always generate all ri and di for all i∈L, just like in the signing algorithm. The verifier can recover all ri from A0 and also recover all di. Due to the completeness of the underlying protocol, the output of the verification algorithm is always 1 when the input of the verification algorithm is the honest signature ν.


### 4.1.2. Public Traceability

Next, we give the proof of public traceability from three cases:(i)
Case 1. Suppose thatM=M′, i=i′. Therefore, we have riT=h1TeiT=h1Tei'T=ri'T, and we get rj=rj′ for all j∈L. In this case, the output of Trace is always linked.(ii)
Case 2. Suppose thatM≠M′,i=i′. So, we have riT=h1TeiT=h1Tei'T=ri'T. However, due to the collision resistance of the hash function g, we have rj≠rj′, for j∈L,j≠i with overwhelming probability. Therefore, only ri=ri′ in the two sequences rjj∈L and rj′j∈L. In this case, the output of Trace is always pki.(iii)
Case 3. Suppose thati≠i′ and M=M′. Thus, we have riT=h1TeiT, h1Tei'T=ri'T, and ri≠ri′. Then, due to the hash function, we have rj≠rj′ for all j∈L with overwhelming probability. If i≠i′ and M≠M′, we obtain ri≠ri′. If the output of the algorithm Trace is not accept, there must be some j≠i,j∈L, satisfying rj=rj′. However, we have rj=A0+gM+⋯+gjM and rj′=A0′+gM′+⋯+gjM′. Due to the collision resistance of hash functions and the difficulty of the GSD problem, the probability of the existence of rj and rj′ is negligible. Therefore, the output of Trace is accept with overwhelming probability.


## 4.1.1. Completeness

The completeness of our TRS is easily verified. Sinceh and g are collision-resistant hash functions, and A0 is generated by the tag and the secret key ei, the signer can always generate all ri and di for all i∈L, just like in the signing algorithm. The verifier can recover all ri from A0 and also recover all di. Due to the completeness of the underlying protocol, the output of the verification algorithm is always 1 when the input of the verification algorithm is the honest signature ν.


## 4.1.2. Public Traceability

Next, we give the proof of public traceability from three cases:(i)
Case 1. Suppose thatM=M′, i=i′. Therefore, we have riT=h1TeiT=h1Tei'T=ri'T, and we get rj=rj′ for all j∈L. In this case, the output of Trace is always linked.(ii)
Case 2. Suppose thatM≠M′,i=i′. So, we have riT=h1TeiT=h1Tei'T=ri'T. However, due to the collision resistance of the hash function g, we have rj≠rj′, for j∈L,j≠i with overwhelming probability. Therefore, only ri=ri′ in the two sequences rjj∈L and rj′j∈L. In this case, the output of Trace is always pki.(iii)
Case 3. Suppose thati≠i′ and M=M′. Thus, we have riT=h1TeiT, h1Tei'T=ri'T, and ri≠ri′. Then, due to the hash function, we have rj≠rj′ for all j∈L with overwhelming probability. If i≠i′ and M≠M′, we obtain ri≠ri′. If the output of the algorithm Trace is not accept, there must be some j≠i,j∈L, satisfying rj=rj′. However, we have rj=A0+gM+⋯+gjM and rj′=A0′+gM′+⋯+gjM′. Due to the collision resistance of hash functions and the difficulty of the GSD problem, the probability of the existence of rj and rj′ is negligible. Therefore, the output of Trace is accept with overwhelming probability.


## 4.2. Security Analysis

We use the security definition of TRS in [5], which formalized security requirements called anonymity, tag-linkability, and exculpability.Theorem 1.
Our scheme is secure in the random oracle model, i.e., satisfying anonymity, tag-linkability, and exculpability.We prove Theorem1 from the following three aspects: proof for anonymity, proof for tag-linkability, and proof for exculpability.


### 4.2.1. Proof for Anonymity

To show that our scheme satisfies anonymity, we define a PPT adversaryA, a challenger C, and a series of games Gi, i=0,1,2,3,4. There are three signing oracles: Signsk0,Signsk1,Signb. The advantage of the adversary A in Gi is denoted by AdvA,Gianon.G0: this game is just like the game defined in (2), in which b=0. The adversary A can access three oracles. The challenger C honestly runs the Signski oracle with corresponding secret keys to reply to A’s queries to these there oracles.G1: let SP,SO be the simulators of the protocol ∏. The challenger C runs SO to simulate the public parameters, instead of running Setup of the protocol ∏. When the adversary A makes queries to Signskb, the challenger C runs SP to answer the query.Due to Definition3, we have(7)AdvA,G0anonλ≈AdvA,G1anonλ.G2: the difference between G2 and G1 is that the challenger C creates an empty table δ. We assume that the sequence r1i,r2i,…,rLi is computed by the user Pi, and i is the position of pki in T. The adversary A gets access to Signskb and the query is T,M.The challenger C does not use h1TebT to get rbb. The challenger C checks whether there is a tuple T,M,r∗b in δ, where r∗b is the vector in δ together with T,M. If the tuple exists, then C uses r∗b and runs the simulator SP to generate the signature. Otherwise, the challenger C randomly chooses a vector rbb←$ℤ2n−k, sets r∗b=rbb, and adds T,M,rbb to δ. Then, the challenger C generates the signature using rbb.Due to the GSD problem, the adversary cannot calculatee from rbb and the public parameters. So, A cannot distinguish G1 and G2:(8)AdvA,G1anonλ≈AdvA,G2anonλ.G3: the difference between G3 and G2 is that the challenger C uses sk1 to generate rj and answers the query to Signskb. G4: the difference between G0 and G4 is the value of b. G4 defines b=1.Due to the zero-knowledge property of the underlying protocol and the hardness of the GSD problem, the outputs of all the above games contain nothing aboutb. Therefore, the adversary can guess the right b with probability 1/2 and the advantage that the adversary A wins the game is negligible.


### 4.2.2. Proof for Tag-Linkability

We assume that the PPT adversary isA and the sequence rii∈L is contained in the signature which can be reconstructed from T,Mi,νi,A0. The L+1 message/signature pairs M1,σ1,…,ML+1,σL+1 with tag T are generated by the adversary A. Suppose that A wins the tag-linkability game. Thus, we have aVerifyσi,Mi,T=1,∀i∈L+1; and bTraceT,Mi,σi,Mj,σj=accept,∀i,j∈L+1,i≠j.LetIreal and ISO be the sets of all the parameters honestly generated in our construction and all the parameters generated by the simulator SO, respectively. Due to the zero-knowledge property of the protocol, A cannot distinguish Ireal and ISo. Therefore, there is an extractor that can extract a witness w=i,ei for each Mi,σi. There is at most only one witness with overwhelming probability because of the hardness of the GSD problem, and correspondingly, siT=HeiT and riT=h1TeiT,i∈L+1. Since T only contains L public keys, there must exist si=sj,i≠j in the sequence pkii∈L+1. Since all public keys in T are distinct, we have ei=ej. Finally, we get riT=h1TeiT=h1TejT=rjT, which means that two signatures σi and σj cannot be accepted by Trace. However, this contradicts our previous assumptions.


### 4.2.3. Proof for Exculpability

Suppose thatA is a PPT adversary. We define the following games Gi,i=0,1.G0: this is the real exculpability game. In this game, the challenger C runs KeyGen to generate pkj,skj, where j is the position of pkj in T. C runs Signskj to reply to A’s queries to Signskj.G1: the challenger C runs the simulator of the protocol ∏ to generate the public parameters and randomly chooses si←$ℤ2n−k. C creates an empty table δ to record each query. The challenger C receives a query T,M to Signskj and the secret key skj corresponds to the public key pkj in T, where HTML translation failed is the position of pkj in T. However, C does not compute rjj in terms of h1TejT. If T,M,r∗j is not in the table δ, where r∗j is the vector in δ together with T,M, he randomly chooses a vector r∗j←$ℤ2n−k and adds T,M,r∗j to the table δ and generates the signature with r∗j. Otherwise, C sets rjj as r∗j and uses the simulator SP to generate the signature.Due to the zero-knowledge property of the underlying protocol and the hardness of the GSD problem, the advantage thatA distinguishes G0 and G1 is(9)AdvA,G0exculλ≈AdvA,G1exculλ.Then, we show that a successful attack is impossible inG1. If A can output two valid pairs T,M,σ and T,M′,σ′, the two valid pairs can satisfy:(1)
VerifyT,M,σ=1 and VerifyT,M′,σ′=1,(2)
TraceT,M,σ,M′,σ′=pki, where i is the position of pki in T.We consider the following two cases:(i)
Case 1. Suppose that one of those two pairs can be linked with the tableδ and the pair is T,M′,σ′=ν′,A0′. Therefore, there is a pair T,M∗,σ∗=ν∗,A0 in δ that can be linked with T,M′,σ′=ν′,A0′ where M∗ and σ∗ are the vectors in δ in the target pair and ν∗,A0 are the vectors corresponding to σ∗. We can get a witness w=i′,ei′ from the extractor of the protocol ∏. In this way, the elements in the pair should satisfy si′T=Hei′T, ri′T=h1Tei′T and rj′=A0′+gM′+⋯+gjM′ for all j∈L,j≠i, and due to that the two pairs are linked, s∗=si′ and rj∗=rj′, for all j∈L. However, s∗ is generated by the simulator of the protocol ∏ and the vectors rj∗, j∈L are randomly chosen in ℤ2n−k in G1. Considering the hardness of the GSD problem, the adversary A cannot generate the valid e′ and r′.(ii)
Case 2. Suppose that neither of the two pairs can be associated with the tableδ. So, we have rj=rj′, which means that A0+gM+⋯+gjM=A0′+gM′+⋯+gjM′, for all j∈L. We can also extract the witness i,ei and i′,ei′ from ν and ν′, respectively. We have h1TeiT=riT and h1Tei′T=ri′T, which holds that h1TeiT=h1Tei′T. If i=i′, the Trace will output si. However, ri is chosen randomly in ℤ2n−k in G1, and so A cannot construct a vector ei which satisfies HeiT=siT and h1TeiT=riT. In this condition, we have i≠i′. Due to the hardness of the GSD problem, the probability that the adversary A constructs the valid ei,ei′,ri,ri′ is negligible. Therefore, the adversary A cannot have a successful attack.


## 4.2.1. Proof for Anonymity

To show that our scheme satisfies anonymity, we define a PPT adversaryA, a challenger C, and a series of games Gi, i=0,1,2,3,4. There are three signing oracles: Signsk0,Signsk1,Signb. The advantage of the adversary A in Gi is denoted by AdvA,Gianon.G0: this game is just like the game defined in (2), in which b=0. The adversary A can access three oracles. The challenger C honestly runs the Signski oracle with corresponding secret keys to reply to A’s queries to these there oracles.G1: let SP,SO be the simulators of the protocol ∏. The challenger C runs SO to simulate the public parameters, instead of running Setup of the protocol ∏. When the adversary A makes queries to Signskb, the challenger C runs SP to answer the query.Due to Definition3, we have(7)AdvA,G0anonλ≈AdvA,G1anonλ.G2: the difference between G2 and G1 is that the challenger C creates an empty table δ. We assume that the sequence r1i,r2i,…,rLi is computed by the user Pi, and i is the position of pki in T. The adversary A gets access to Signskb and the query is T,M.The challenger C does not use h1TebT to get rbb. The challenger C checks whether there is a tuple T,M,r∗b in δ, where r∗b is the vector in δ together with T,M. If the tuple exists, then C uses r∗b and runs the simulator SP to generate the signature. Otherwise, the challenger C randomly chooses a vector rbb←$ℤ2n−k, sets r∗b=rbb, and adds T,M,rbb to δ. Then, the challenger C generates the signature using rbb.Due to the GSD problem, the adversary cannot calculatee from rbb and the public parameters. So, A cannot distinguish G1 and G2:(8)AdvA,G1anonλ≈AdvA,G2anonλ.G3: the difference between G3 and G2 is that the challenger C uses sk1 to generate rj and answers the query to Signskb. G4: the difference between G0 and G4 is the value of b. G4 defines b=1.Due to the zero-knowledge property of the underlying protocol and the hardness of the GSD problem, the outputs of all the above games contain nothing aboutb. Therefore, the adversary can guess the right b with probability 1/2 and the advantage that the adversary A wins the game is negligible.


## 4.2.2. Proof for Tag-Linkability

We assume that the PPT adversary isA and the sequence rii∈L is contained in the signature which can be reconstructed from T,Mi,νi,A0. The L+1 message/signature pairs M1,σ1,…,ML+1,σL+1 with tag T are generated by the adversary A. Suppose that A wins the tag-linkability game. Thus, we have aVerifyσi,Mi,T=1,∀i∈L+1; and bTraceT,Mi,σi,Mj,σj=accept,∀i,j∈L+1,i≠j.LetIreal and ISO be the sets of all the parameters honestly generated in our construction and all the parameters generated by the simulator SO, respectively. Due to the zero-knowledge property of the protocol, A cannot distinguish Ireal and ISo. Therefore, there is an extractor that can extract a witness w=i,ei for each Mi,σi. There is at most only one witness with overwhelming probability because of the hardness of the GSD problem, and correspondingly, siT=HeiT and riT=h1TeiT,i∈L+1. Since T only contains L public keys, there must exist si=sj,i≠j in the sequence pkii∈L+1. Since all public keys in T are distinct, we have ei=ej. Finally, we get riT=h1TeiT=h1TejT=rjT, which means that two signatures σi and σj cannot be accepted by Trace. However, this contradicts our previous assumptions.


## 4.2.3. Proof for Exculpability

Suppose thatA is a PPT adversary. We define the following games Gi,i=0,1.G0: this is the real exculpability game. In this game, the challenger C runs KeyGen to generate pkj,skj, where j is the position of pkj in T. C runs Signskj to reply to A’s queries to Signskj.G1: the challenger C runs the simulator of the protocol ∏ to generate the public parameters and randomly chooses si←$ℤ2n−k. C creates an empty table δ to record each query. The challenger C receives a query T,M to Signskj and the secret key skj corresponds to the public key pkj in T, where HTML translation failed is the position of pkj in T. However, C does not compute rjj in terms of h1TejT. If T,M,r∗j is not in the table δ, where r∗j is the vector in δ together with T,M, he randomly chooses a vector r∗j←$ℤ2n−k and adds T,M,r∗j to the table δ and generates the signature with r∗j. Otherwise, C sets rjj as r∗j and uses the simulator SP to generate the signature.Due to the zero-knowledge property of the underlying protocol and the hardness of the GSD problem, the advantage thatA distinguishes G0 and G1 is(9)AdvA,G0exculλ≈AdvA,G1exculλ.Then, we show that a successful attack is impossible inG1. If A can output two valid pairs T,M,σ and T,M′,σ′, the two valid pairs can satisfy:(1)
VerifyT,M,σ=1 and VerifyT,M′,σ′=1,(2)
TraceT,M,σ,M′,σ′=pki, where i is the position of pki in T.We consider the following two cases:(i)
Case 1. Suppose that one of those two pairs can be linked with the tableδ and the pair is T,M′,σ′=ν′,A0′. Therefore, there is a pair T,M∗,σ∗=ν∗,A0 in δ that can be linked with T,M′,σ′=ν′,A0′ where M∗ and σ∗ are the vectors in δ in the target pair and ν∗,A0 are the vectors corresponding to σ∗. We can get a witness w=i′,ei′ from the extractor of the protocol ∏. In this way, the elements in the pair should satisfy si′T=Hei′T, ri′T=h1Tei′T and rj′=A0′+gM′+⋯+gjM′ for all j∈L,j≠i, and due to that the two pairs are linked, s∗=si′ and rj∗=rj′, for all j∈L. However, s∗ is generated by the simulator of the protocol ∏ and the vectors rj∗, j∈L are randomly chosen in ℤ2n−k in G1. Considering the hardness of the GSD problem, the adversary A cannot generate the valid e′ and r′.(ii)
Case 2. Suppose that neither of the two pairs can be associated with the tableδ. So, we have rj=rj′, which means that A0+gM+⋯+gjM=A0′+gM′+⋯+gjM′, for all j∈L. We can also extract the witness i,ei and i′,ei′ from ν and ν′, respectively. We have h1TeiT=riT and h1Tei′T=ri′T, which holds that h1TeiT=h1Tei′T. If i=i′, the Trace will output si. However, ri is chosen randomly in ℤ2n−k in G1, and so A cannot construct a vector ei which satisfies HeiT=siT and h1TeiT=riT. In this condition, we have i≠i′. Due to the hardness of the GSD problem, the probability that the adversary A constructs the valid ei,ei′,ri,ri′ is negligible. Therefore, the adversary A cannot have a successful attack.


## 5. Efficiency

In this section, we consider the efficiency of our scheme in three aspects: public key sizes, secret key sizes, and signature sizes.(1)
Public key size: the public key in our scheme consists ofH,B∈ℤ2n−k×n×ℤ2r×m and vectors si∈ℤ2n−k, for i∈L. The public key size of our scheme is n2−kn+L+rm+Ln bits.(2)
Secret key size: the secret key of each signerPi is a vector ei∈ℤ2n, and the bit length of ei is n.(3)
Signature size: the signature size in our scheme is determined by the proofν, and the bit length of the signature is Oλ·logL. Specifically, the signature size of our scheme includes the following three aspects: i the size of three hash values and three commitments is 6λ bits, where λ is the security parameter. ii For each case, b=0,b=1, or b=2, the size of response is 4lm+4nl−2n+2λ bits, where l=logL. iii The bit size of the vector A0 is n−k. The repetition number of Acc-GStern’s protocol is defined as p (for example, if the cheating probability of Acc-GStern’s protocol is approximately 2−128, p=220). To sum up, the signature size of our scheme is 6λ+4lmp+4nlp−2np+2pλ+n−k bits. Since l=logL and L is the ring size, our signature size is logarithmic in the ring size.According to decoding attacks in [34–36], we set the parameters of our scheme under 128 bit and 256 bit security in Table 1.Table 1
Our TRS scheme.
Schemenktck′rLpPk size (bit)Signature size (bit)Security12400200658889650932203.0×1077.9×107128241503307132141792102434404.2×1091.1×1010256We give the implementation of our scheme on an Intel(R) Core(TM) i5-1035G1 CPU @ 2.20 GHz, and we implemented our scheme based on Python. We use the first set of parameters in Table1 to implement our scheme. The running time of KeyGen to generate a pair of pk,sk is about 3 ms. However, due to the use of the hash function defined in Definition 4, the total running time for our signature scheme to generate a signature is about 2 minutes.Since our scheme is an improvement over [10], the signature size in the original scheme is linear in the number of ring size, while the signature size of our scheme is logarithmic in the ring size. To the best of our knowledge, there are no other code-based TRS schemes. However, for some applications, the key and signature sizes of our scheme are still large. Finding new techniques to reduce the sizes of code-based traceable ring signature schemes and improve the efficiency of code-based traceable ring signature schemes are our future research direction.


## 6. Conclusion

In this paper, we construct a new code-based TRS scheme. The signature size of our scheme is logarithmic in the size of the ring. We then provide the tag-linkability, anonymity, and exculpability of our scheme and so our scheme is secure in the random oracle model under the assumption of the hardness of the SD problem and the 2-RNSD problem.



---

*Source: 3938321-2022-04-29.xml*