# An Efficient Code-Based Threshold Ring Signature Scheme with a Leader-Participant Model

Authors: Guomin Zhou; Peng Zeng; Xiaohui Yuan; Siyuan Chen; Kim-Kwang Raymond Choo
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Digital signature schemes with additional properties have broad applications, such as in protecting the identity of signers allowing a signer to anonymously sign a message in a group of signers (also known as a ring). While these number-theoretic problems are still secure at the time of this research, the situation could change with advances in quantum computing. There is a pressing need to design PKC schemes that are secure against quantum attacks. In this paper, we propose a novel code-based threshold ring signature scheme with a leader-participant model. A leader is appointed, who chooses some shared parameters for other signers to participate in the signing process. This leader-participant model enhances the performance because every participant including the leader could execute the decoding algorithm (as a part of signing process) upon receiving the shared parameters from the leader. The time complexity of our scheme is close to Courtois et al.’s (2001) scheme. The latter is often used as a basis to construct other types of code-based signature schemes. Moreover, as a threshold ring signature scheme, our scheme is as efficient as the normal code-based ring signature.


---

## Body

## 1. Introduction

Public-key cryptographic (PKC) method remains a topic of research interest partly due to its role in our increasingly digitalized society and the challenge of designing efficient and provably secure schemes with additional features required in contemporary applications. Existing PKC schemes are generally based on the hardness of number theory problems, such as factorization and discrete logarithm problems. While these number-theoretic problems are still secure at the time of this research, the situation could change with advances in quantum computing. For example, in the 1990s, Shor presented a quantum attack algorithm that could be used to solve both factorization and discrete logarithm problems in polynomial time with quantum computers [1, 2]. Thus, there is a pressing need to design PKC schemes that are secure against quantum attacks. Code-based PKC schemes, established by McEliece in 1978 [3], are one kind of such postquantum PKC schemes. Code-based PKC schemes are based on hard problems in coding theory and are considered as an appropriate solution to keep the message secure in the quantum era.In 2001, Rivest et al. presented the ring signature as a digital signature scheme with additional property [4]. In a ring signature scheme, each member of the ring has a unique public-private key pair. For a message m, any signer in the ring is able to generate a signature on m with the private key and the ring public key which consists of the public keys of all signers in the ring. The user could only verify the validation of the signature without knowing who the true signer of the message m is; thus, it preserves the anonymity of the signer. Due to this property, ring signature has many potential applications in real-world scenarios. One practical application is a company soliciting opinions from its employees. In order to improve the reliability of employee feedback, it is often necessary for multiple employees (which can be thousands in a large multinational corporation or company) to submit their opinions. At the same time, in order to prevent the retaliation of senior management or line supervisor, the true identity of the participating employees should not be revealed. Threshold ring signature is one appropriate solution for such an application, which enables the employees to reach a certain quantity to jointly generate a valid signature. Ring signature can also be used for data sharing in the cloud [5] and for privacy-preserving public auditing of shared data [6].Since the notion of ring signatures was introduced, there have been a number of ring signature schemes proposed in the literature. Shacham and Waters [7] presented the first efficient ring signature scheme based on bilinear groups. The scheme is anonymous against full key exposure and unforgeable with respect to insider corruption. Kar [8] proposed an online/offline ring signature scheme whose security is based on both computational Diffie-Hellman and k-CAA problems. The scheme satisfies signer ambiguity and enables the misbehavior of the signer to be detected. Wang et al. [9] presented a new concept of identity-based quotable ring signature which could be used to derive new ring signatures on substrings of an original message from an original ring signature on the original message. The scheme is based on bilinear pairing of composite order and proven to be secure under the assumption that the subgroup decision problem and computational Diffie-Hellman problem are hard. Zeng et al. [10]. proposed an efficient noninteractive deniable ring signature scheme and proved its security in the standard model. Nevertheless, all the aforementioned schemes [7–10] are based on the hard problems in number theory and thus will became insecure as soon as large quantum computers are built. There are also some alternative ring signature schemes that are based on the hard problems not affected by quantum computer attacks, such as the schemes based on NTRU lattices [11] and based on multivariate quadratic polynomials [12].Bresson et al. extended the notion of ring signatures into threshold ring signatures, which are increasingly popular due to their practical utilities in comparison to the conventional ring signatures [13]. Similar to ring signature schemes, a (t,N) threshold ring signature scheme allows at least t signers in the ring of N signers to cooperate with each other to sign a message without leaking any identity information of the t signers. Existing threshold ring signature schemes are mostly based on the number theory [14–17]; hence, as mentioned above, such schemes could be insecure in the quantum world. To the best of our knowledge, Dallot and Vergnaud’s scheme [18] and Aguilar Melchor et al.’s scheme [19] are the only two code-based threshold ring signature schemes published in the literature. Dallot and Vergnaud’s scheme [18] combined Bresson et al.’s construction [13] and Courtois et al.’s signature [20], which results in the signature size twice the number of system users. Aguilar Melchor et al.’s scheme [19] is a generalization of Stern’s identification and signature scheme [21] and has low efficiency in the signature size.In this paper, we propose a novel code-based(t,N) threshold ring signature scheme. The security of our proposed scheme is based on the hardness of the syndrome decoding (SD) problem (known to be an NP-complete problem) and the indistinguishability of Goppa codes from random linear codes. In the proposed scheme, a leader is appointed from the t signers, who chooses some shared parameters for other t-1 signers to participate in the signing process. This leader-participant model enhances the performance because every participant including the leader could execute the decoding algorithm (as a part of signing process) concurrently and immediately upon receiving the shared parameters from the leader.The rest of this paper is organized as follows: Section2 presents background information and preliminaries. Section 3 describes our proposed method, whose security analysis is presented in Section 4 and efficiency is evaluated in Section 5. Conclusion is presented in Section 6.


## 2. Preliminaries

### 2.1. Definitions and Problems in Coding Theory

For the rest of this paper, we consider linear codes over binary fieldF2.Definition 1 (weight).
The (Hamming) weight of a vector (or word)c∈F2n, denoted by wt(c), is the number of nonzero bits in c.Definition 2 (code).
An[n,k,d] (linear) code C is a linear k-dimensional subspace of F2n with minimum distance d, which is defined as (1)d=minc1≠c2∈Cwtc1-c2. An [n,k,d] code has the ⌊(d-1)/2⌋-error-correcting capability.Definition 3 (generator matrix and parity-check matrix).
A generator matrixG of an [n,k,d] code C is a k×n matrix whose rows form a basis of C. A parity-check matrix H of C is a generator matrix of the dual of C, which has the order (n-k)×n.The security of our threshold ring signature scheme is based on the following two hard problems in coding theory. Letεn,w denote the set of all vectors of length n and weight w.Problem 4 (Syndrome Decoding (SD)).
Input. It includes an integer w, a vector s∈F2r, and a r×n random binary matrix H.
Property. Find a vector e∈εn,w such that(2)HeT=sT, where vT denotes the transpose of vector (or matrix) v. The advantage of adversary A solves the SD problem denoted by AdvSD(A), which is negligible since the SD problem was proven to be NP-complete in [22].To describe the following Goppa Code Distinguishing (GCD) problem, we denote byG0=Goppa(n-k,n) the set of parity-check matrices of all binary irreducible [n,k] Goppa codes and G1=Rand(n-k,n) the set of the parity-check matrices of all random binary [n,k] linear codes. Set G=G0∪G1.Problem 5 (Goppa Code Distinguishing (GCD)).
Input. A matrix H is randomly chosen from set G.
Property. Return b s.t. H∈Gb.
LetD be a probabilistic polynomial time (PPT) distinguisher for the GCD problem. The advantage, denoted by Advn,k(D), of D is defined as follows: (3)Advn,kD=Pr⁡DH=b∣b⟵R0,1,H⟵Gb-12. The indistinguishability assumption of the GCD problem holds if Advn,k(D) is negligible.


### 2.2.(t,N) Threshold Ring Signature

We use the formal definition of threshold ring signature scheme following the work of Bresson et al. [13]. Let us assume that there are N signers Si, 1≤i≤N, forming a ring R and the threshold of generating a valid signature is t with t<N. For simplicity, we assume the first t signers S1,…,St are the true signers in R. A (t,N) threshold ring signature scheme consists of four algorithms (Setup, KeyGen, Sign, Verify).S
e
t
u
p
(
λ
). The algorithm takes as input a security parameter λ and outputs the system public parameter P.K
e
y
G
e
n
(
P
). The algorithm takes as input the parameter P and generates N pairs of public-private key (pki,ski) for the signers Si∈R, 1≤i≤N. The N public keys pki, 1≤i≤N, form the ring public key PK={pk1,pk2,…,pkN} and each private key ski is sent to the signer Si via a secure channel, 1≤i≤N.S
i
g
n
(
m
,
P
,
P
K
,
T
S
K
). The algorithm takes as input a message m, the parameter P, the ring public key PK, and a private key set TSK={sk1,…,skt} of t singers and outputs a threshold ring signature σ on m.V
e
r
i
f
y
(
m
,
P
K
,
σ
). The algorithm takes as input the message m, the ring public key PK, and the threshold ring signature σ and outputs 1 if (m, σ) is a valid message-signature pair. Otherwise, the algorithm outputs 0.


### 2.3. Security Model

A threshold ring signature scheme needs to satisfy the correctness, anonymity, and unforgeability properties.Correctness. We say that a (t,N) ring signature scheme satisfies the correctness property if, for any valid t private key set TSK and message m, the following equation holds: (4)Verifym,PK,Signm,P,PK,TSK=1.Anonymity. We say that a (t,N) ring signature scheme satisfies the anonymity property if, for a given message-signature pair (m,σ), any attacker A has only the probability 1/Nt to determine the real signers participating in the signing process. More formally, the anonymity says that, for two message-signature pairs (m,σ0) and (m,σ1) signed by two signer sets {S01,…,S0t} and {S11,…,S1t}, respectively, the following absolute value is negligible: (5)PrAσb=b∣b⟵R0,1,σb⟵Sb1,…,Sbt-12.Unforgeability. To define unforgeability, we introduce an attack model of (t,N) threshold ring signatures. A PPT forger F is allowed to access a corruption oracle, a signature oracle, and a hash oracle and make adaptively queries on them. After the corruption queries, F can obtain at most t-1 private keys of ring members. F can also use the signature queries to obtain threshold ring signatures for messages and signers chosen by F. Then, F attempts to forge a signature σ′ on a chosen message m′ (note that σ′ is not allowed to be an output of some signature oracle). We say that a (t,N) threshold ring signature scheme satisfies the unforgeability property if, for any PPT attacker F, the probability, denoted by SuccF, that F succeeds in this attack is negligible.We remark that there is a special signer, referred to as leader, in our(t,N) threshold ring signature scheme. The leader is randomly chosen during each sign process without any additional privileges. The leader in our scheme must act honestly. Otherwise, anonymity of t participating signers cannot be achieved.


## 2.1. Definitions and Problems in Coding Theory

For the rest of this paper, we consider linear codes over binary fieldF2.Definition 1 (weight).
The (Hamming) weight of a vector (or word)c∈F2n, denoted by wt(c), is the number of nonzero bits in c.Definition 2 (code).
An[n,k,d] (linear) code C is a linear k-dimensional subspace of F2n with minimum distance d, which is defined as (1)d=minc1≠c2∈Cwtc1-c2. An [n,k,d] code has the ⌊(d-1)/2⌋-error-correcting capability.Definition 3 (generator matrix and parity-check matrix).
A generator matrixG of an [n,k,d] code C is a k×n matrix whose rows form a basis of C. A parity-check matrix H of C is a generator matrix of the dual of C, which has the order (n-k)×n.The security of our threshold ring signature scheme is based on the following two hard problems in coding theory. Letεn,w denote the set of all vectors of length n and weight w.Problem 4 (Syndrome Decoding (SD)).
Input. It includes an integer w, a vector s∈F2r, and a r×n random binary matrix H.
Property. Find a vector e∈εn,w such that(2)HeT=sT, where vT denotes the transpose of vector (or matrix) v. The advantage of adversary A solves the SD problem denoted by AdvSD(A), which is negligible since the SD problem was proven to be NP-complete in [22].To describe the following Goppa Code Distinguishing (GCD) problem, we denote byG0=Goppa(n-k,n) the set of parity-check matrices of all binary irreducible [n,k] Goppa codes and G1=Rand(n-k,n) the set of the parity-check matrices of all random binary [n,k] linear codes. Set G=G0∪G1.Problem 5 (Goppa Code Distinguishing (GCD)).
Input. A matrix H is randomly chosen from set G.
Property. Return b s.t. H∈Gb.
LetD be a probabilistic polynomial time (PPT) distinguisher for the GCD problem. The advantage, denoted by Advn,k(D), of D is defined as follows: (3)Advn,kD=Pr⁡DH=b∣b⟵R0,1,H⟵Gb-12. The indistinguishability assumption of the GCD problem holds if Advn,k(D) is negligible.


## 2.2.(t,N) Threshold Ring Signature

We use the formal definition of threshold ring signature scheme following the work of Bresson et al. [13]. Let us assume that there are N signers Si, 1≤i≤N, forming a ring R and the threshold of generating a valid signature is t with t<N. For simplicity, we assume the first t signers S1,…,St are the true signers in R. A (t,N) threshold ring signature scheme consists of four algorithms (Setup, KeyGen, Sign, Verify).S
e
t
u
p
(
λ
). The algorithm takes as input a security parameter λ and outputs the system public parameter P.K
e
y
G
e
n
(
P
). The algorithm takes as input the parameter P and generates N pairs of public-private key (pki,ski) for the signers Si∈R, 1≤i≤N. The N public keys pki, 1≤i≤N, form the ring public key PK={pk1,pk2,…,pkN} and each private key ski is sent to the signer Si via a secure channel, 1≤i≤N.S
i
g
n
(
m
,
P
,
P
K
,
T
S
K
). The algorithm takes as input a message m, the parameter P, the ring public key PK, and a private key set TSK={sk1,…,skt} of t singers and outputs a threshold ring signature σ on m.V
e
r
i
f
y
(
m
,
P
K
,
σ
). The algorithm takes as input the message m, the ring public key PK, and the threshold ring signature σ and outputs 1 if (m, σ) is a valid message-signature pair. Otherwise, the algorithm outputs 0.


## 2.3. Security Model

A threshold ring signature scheme needs to satisfy the correctness, anonymity, and unforgeability properties.Correctness. We say that a (t,N) ring signature scheme satisfies the correctness property if, for any valid t private key set TSK and message m, the following equation holds: (4)Verifym,PK,Signm,P,PK,TSK=1.Anonymity. We say that a (t,N) ring signature scheme satisfies the anonymity property if, for a given message-signature pair (m,σ), any attacker A has only the probability 1/Nt to determine the real signers participating in the signing process. More formally, the anonymity says that, for two message-signature pairs (m,σ0) and (m,σ1) signed by two signer sets {S01,…,S0t} and {S11,…,S1t}, respectively, the following absolute value is negligible: (5)PrAσb=b∣b⟵R0,1,σb⟵Sb1,…,Sbt-12.Unforgeability. To define unforgeability, we introduce an attack model of (t,N) threshold ring signatures. A PPT forger F is allowed to access a corruption oracle, a signature oracle, and a hash oracle and make adaptively queries on them. After the corruption queries, F can obtain at most t-1 private keys of ring members. F can also use the signature queries to obtain threshold ring signatures for messages and signers chosen by F. Then, F attempts to forge a signature σ′ on a chosen message m′ (note that σ′ is not allowed to be an output of some signature oracle). We say that a (t,N) threshold ring signature scheme satisfies the unforgeability property if, for any PPT attacker F, the probability, denoted by SuccF, that F succeeds in this attack is negligible.We remark that there is a special signer, referred to as leader, in our(t,N) threshold ring signature scheme. The leader is randomly chosen during each sign process without any additional privileges. The leader in our scheme must act honestly. Otherwise, anonymity of t participating signers cannot be achieved.


## 3. Our Threshold Ring Signature Scheme

For simplicity, we denotev1≤i≤N to be the sequence v1,v2,…,vN. Our code-based (t,N) threshold ring signature scheme can be described as follows.S
e
t
u
p
(
λ
). Given a security parameter λ, the algorithm chooses integers n, k, d, and w to, respectively, represent length, dimension, minimum distance, and error-correcting ability of the code underpinning our scheme. The algorithm outputs the system public parameter, P=(n,k,d,w).K
e
y
G
e
n
(
P
). Given P=(n,k,d,w), the algorithm performs the following:(i)
For each signerSi in the ring R={Si|1≤i≤N}, choose a parity-check matrix Hi of a w-error-correcting irreducible [n,k,d] Goppa code, which has a corresponding fast decoding algorithm DECHi, 1≤i≤N.(ii)
For each signerSi∈R, choose a random binary (n-k)×(n-k) invertible matrix Qi and a random permutation n×n matrix Pi, 1≤i≤N.(iii)
Compute(6)H~i=QiHiPi,1≤i≤N.(iv)
For each signerSi∈R, set the private key ski=(Qi,Hi,Pi,DECHi) and public key pki=H~i, 1≤i≤N. The ring public key is (7)PK=H~1≤i≤N=H~1,H~2…,H~Nand each private keyski=(Qi,Hi,Pi,DECHi) is sent to the signer Si via a secure channel, 1≤i≤N.S
i
g
n
(
m
,
P
,
P
K
,
T
S
K
). Given message m, system parameter P, ring public key PK=(H~1≤i≤N), and private key set TSK=(sk1≤i≤t) of t signers, where ski=(Qi,Hi,Pi,DECHi) for each 1≤i≤t, the algorithm first elects a leader Sl randomly from the involved signer set {Si|1≤i≤t}. Note that Sl is just a signer participating in the signing process without any additional privileges. The signing processes are executed as follows:(i)
For eachSi, 1≤i≠l≤t, randomly choose eij∈F2n, j=t+1,t+2,…,N, and compute(8)siT=hmT+∑j=t+1NH~jeijT,1≤i≠l≤t,whereh:{0,1}∗→{0,1}n-k is a one-way collision-resistant hash function.(ii)
For eachSi, 1≤i≠l≤t, compute Qi-1siT. If Qi-1siT is a decodable syndrome, compute DECHi(Qi-1siT) to obtain a vector ei′ such that(9)Hiei′T=Qi-1siT,1≤i≠l≤t.Otherwise, return to the previous step to recomputesi.(iii)
Compute(10)eiT=PiTei′T,1≤i≠l≤t.For all signersSi, 1≤i≠l≤t, the above signing processes can be concurrent.(iv)
EachSi sends N-t+1 generated vectors (ei,ei(t+1),ei(t+2),…,eiN), 1≤i≠l≤t, to the leader Sl.(v)
Upon receiving all vectors(ei,ei(t+1),ei(t+2),…,eiN), 1≤i≠l≤t, Sl executes the following steps:
(a)
For eacht+1≤j≤N, choose a random elj under the condition wt(elj+∑i=1,i≠lt‍eij)=w. Set(11)ej=∑i=1teij,t+1≤j≤N.(b)
Ift is an odd number, then compute(12)slT=hmT+∑j=t+1NH~jeljT.Otherwise (i.e.,t is an even number), compute(13)slT=∑j=t+1NH~jeljT.(c)
ComputeQl-1slT. If Ql-1slT is a decodable syndrome, compute DECHl(Ql-1slT) to obtain an vector el′ such that(14)Hlel′T=Ql-1slT.Otherwise, return to the first step executed bySl to choose another elj.(d)
Compute(15)elT=PlTel′T.(e)
Outputσ=(e1,e2,…,eN) as the threshold ring signature on the message m.V
e
r
i
f
y
(
m
,
P
K
,
σ
). Given the ring public key PK=(H~1≤i≤N) and a message-signature pair (m,σ=(e1,e2,…,eN)), the verifier can check the validity of σ by executing the following steps:(i)
Check ifei∈εn,w holds for each 1≤i≤N. If it does not, output 0 and terminate the verification process.(ii)
Check if(16)hmT=∑i=1NH~ieiTholds. If it holds, output1, and 0, otherwise.


## 4. Security Analysis

In the section, we analyze the security of our scheme, based on the security model defined in Section2.3.


### 4.1. Correctness

Let(m,σ=(e1,e2,…,eN)) be a valid message-signature pair generated by t signers Si, i=1,2,…,t, as in Section 3. First, it is clear that each ei has length n and weight w, based on our construction (see (10), (11), and (15)). Thus, ei∈εn,w holds for each 1≤i≤N. Now it remains to show (16): h(m)T=∑i=1N‍H~ieiT. Starting from the right side of the equation, we have (17)∑i=1NH~ieiT=∑i=1tH~ieiT+∑i=t+1NH~ieiT=6∑i=1tQiHiPieiT+∑i=t+1NH~ieiT=10,15∑i=1tQiHiei′T+∑i=t+1NH~ieiT=9,14∑i=1tsiT+∑i=t+1NH~ieiT=slT+∑i=1,i≠ltsiT+∑i=t+1NH~ieiT=8slT+t-1hmT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT. Next, we consider two cases with respect to the value of t. Recall that all the operations in this paper are executed over the binary field F2. If t is an odd number, then we have (18)∑i=1NH~ieiT=slT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=12hmT+∑j=t+1NH~jeljT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=hmT+∑j=t+1NH~jeljT+∑i=1,i≠ltH~jeijT+∑i=t+1NH~ieiT=11hmT+∑j=t+1NH~jejT+∑i=t+1NH~ieiT=hmT. Otherwise (i.e., t is an even number), we have (19)∑i=1NH~ieiT=slT+hmT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=13∑j=t+1NH~jeljT+hm+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=11hmT+∑j=t+1NH~jejT+∑i=t+1NH~ieiT=hmT. To sum up, we have h(m)T=∑i=1N‍H~ieiT for both cases of t. Together with the relation ei∈εn,w, 1≤i≤N, we have (20)Verifym,PK,σ=1. This demonstrates that our threshold ring signature scheme satisfies the correctness property.


### 4.2. Anonymity

Assume that there is an adversaryA who receives two valid message-signature pairs (m,σ0=(e01,e02,…,e0N)) and (m,σ1=(e11,e12,…,e1N)) generated by two sets {S01,…,S0t} and {S11,…,S1t} of signers, respectively. From the view of A, each vector ebi, b=0,1, i=1,2,…,N, in the signatures σ0 or σ1 is completely random. This results in a negligible absolute value Pr[A(σb)=b|b←R{0,1},σb←{Sb1,…,Sbt}]-1/2 and, hence, our threshold ring signature scheme satisfies the anonymity property.


### 4.3. Unforgeability

We prove the unforgeability using the attack model in Section2.3. Let F be a PPT algorithm that has a nonnegligible probability SuccF in attacking our proposed (t,N) threshold ring signature scheme. Using F, we construct another PPT algorithm C to solve the SD problem with nonnegligible advantage. That is, given a random (n-k)×n matrix H′ and a random decodable syndrome s′, C can find a vector e′∈εn,w, s.t. H′e′T=s′T. Thus, C plays the following games with F.Game 0. C randomly chooses an index l from {1,2,…,N} and sets the public key PKl of the signer Sl as H′. For all other signers, C chooses N-1 parity-check matrices, denoted by Hi  (1≤i≤N,i≠l), of random permuted Goppa codes as their public keys and the corresponding private keys will not be used. After that, C sends all N matrices to F. F queries the hash oracle and the sign oracle several times and seeks to obtain a valid signature for some message. We denote the probability that F wins Game 0 by Pr(G0).Game 1. C replaces the original hash function with the hash simulator H. C can respond to F as follows.WhenF makes a query to the hash simulator H, H stores an index r in a list Λ(m) associated with message m. If Λ(m) is empty, then H just chooses a random vector el∈F2n and computes slT=H′elT+Σi=1,i≠lNHieiT as the output of the simulator. Otherwise (i.e., r=Λ(M)), H picks a random el from εn,w and computes slT=H′elT+Σi=1,i≠lNHieiT as the output of the simulator. In both cases, H outputs a random slT. So we have the probability that F wins Game 1 equal to Pr(G1)=Pr(G0).Game 2. C replaces the signature oracle with the signing simulator Sim. C can respond to F as follows.WhenF makes a query to Sim on message m, Sim chooses a random index r∈F2 and sets Λ(m)=r. Then, C runs H with input m. If there is no el∈εn,w, then Sim aborts; otherwise, Sim outputs el and sets Λ(m) empty.Game 2 differs from Game 1 only in the case thatSim aborts. The probability that Sim aborts is at most qSim/2n, where qSim represents the maximum query times to the Sim. It follows that the probability, denoted by Pr(G2), of F winning Game 2 satisfies (21)PrG1-PrG2≤qSim2n.Game 3. C replaces the public key (the permuted parity-check matrix of random Goppa codes) with the parity-check matrix of random linear code for each signer in this game. According to the indistinguishability assumption (see Section 2), F has only a negligible advantage Advn,k(F) in solving the GCD problem. That is, we have the probability that F wins Game 3 as |Pr(G3)-Pr(G2)|=Advn,k(F).Game 4. The wining condition is changed in this game. C picks a random number k in {1,…,qH}, where qH is the maximum query times to H. F should generate the k-th forgery message-signature pair which can pass the verification. Hence, the probability of F wining this game is Pr(G4)=Pr(G3)/qH.We remark that ifF wins Game 4, then F is able to inverse the SD problem (i.e., find a vector e′∈εn,w s.t. H′e′T=s′T). Hence, we have Pr(G4)=AdvSD(C).Combining all these together, we haveSuccF=Pr(G0) and (22)qHAdvSDC+Advn,kF≥SuccF+qSim2n. In other words, if there is a PPT forger F which can forge a valid message-signature pair with a nonnegligible probability in attacking our scheme, then we can construct a PPT algorithm C to inverse the SD problem with a nonnegligible probability. Thus, we can conclude that our proposed threshold ring signature scheme is existentially unforgeable under the chosen message attack if both the GCD problem and SD problem are hard.


## 4.1. Correctness

Let(m,σ=(e1,e2,…,eN)) be a valid message-signature pair generated by t signers Si, i=1,2,…,t, as in Section 3. First, it is clear that each ei has length n and weight w, based on our construction (see (10), (11), and (15)). Thus, ei∈εn,w holds for each 1≤i≤N. Now it remains to show (16): h(m)T=∑i=1N‍H~ieiT. Starting from the right side of the equation, we have (17)∑i=1NH~ieiT=∑i=1tH~ieiT+∑i=t+1NH~ieiT=6∑i=1tQiHiPieiT+∑i=t+1NH~ieiT=10,15∑i=1tQiHiei′T+∑i=t+1NH~ieiT=9,14∑i=1tsiT+∑i=t+1NH~ieiT=slT+∑i=1,i≠ltsiT+∑i=t+1NH~ieiT=8slT+t-1hmT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT. Next, we consider two cases with respect to the value of t. Recall that all the operations in this paper are executed over the binary field F2. If t is an odd number, then we have (18)∑i=1NH~ieiT=slT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=12hmT+∑j=t+1NH~jeljT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=hmT+∑j=t+1NH~jeljT+∑i=1,i≠ltH~jeijT+∑i=t+1NH~ieiT=11hmT+∑j=t+1NH~jejT+∑i=t+1NH~ieiT=hmT. Otherwise (i.e., t is an even number), we have (19)∑i=1NH~ieiT=slT+hmT+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=13∑j=t+1NH~jeljT+hm+∑i=1,i≠lt∑j=t+1NH~jeijT+∑i=t+1NH~ieiT=11hmT+∑j=t+1NH~jejT+∑i=t+1NH~ieiT=hmT. To sum up, we have h(m)T=∑i=1N‍H~ieiT for both cases of t. Together with the relation ei∈εn,w, 1≤i≤N, we have (20)Verifym,PK,σ=1. This demonstrates that our threshold ring signature scheme satisfies the correctness property.


## 4.2. Anonymity

Assume that there is an adversaryA who receives two valid message-signature pairs (m,σ0=(e01,e02,…,e0N)) and (m,σ1=(e11,e12,…,e1N)) generated by two sets {S01,…,S0t} and {S11,…,S1t} of signers, respectively. From the view of A, each vector ebi, b=0,1, i=1,2,…,N, in the signatures σ0 or σ1 is completely random. This results in a negligible absolute value Pr[A(σb)=b|b←R{0,1},σb←{Sb1,…,Sbt}]-1/2 and, hence, our threshold ring signature scheme satisfies the anonymity property.


## 4.3. Unforgeability

We prove the unforgeability using the attack model in Section2.3. Let F be a PPT algorithm that has a nonnegligible probability SuccF in attacking our proposed (t,N) threshold ring signature scheme. Using F, we construct another PPT algorithm C to solve the SD problem with nonnegligible advantage. That is, given a random (n-k)×n matrix H′ and a random decodable syndrome s′, C can find a vector e′∈εn,w, s.t. H′e′T=s′T. Thus, C plays the following games with F.Game 0. C randomly chooses an index l from {1,2,…,N} and sets the public key PKl of the signer Sl as H′. For all other signers, C chooses N-1 parity-check matrices, denoted by Hi  (1≤i≤N,i≠l), of random permuted Goppa codes as their public keys and the corresponding private keys will not be used. After that, C sends all N matrices to F. F queries the hash oracle and the sign oracle several times and seeks to obtain a valid signature for some message. We denote the probability that F wins Game 0 by Pr(G0).Game 1. C replaces the original hash function with the hash simulator H. C can respond to F as follows.WhenF makes a query to the hash simulator H, H stores an index r in a list Λ(m) associated with message m. If Λ(m) is empty, then H just chooses a random vector el∈F2n and computes slT=H′elT+Σi=1,i≠lNHieiT as the output of the simulator. Otherwise (i.e., r=Λ(M)), H picks a random el from εn,w and computes slT=H′elT+Σi=1,i≠lNHieiT as the output of the simulator. In both cases, H outputs a random slT. So we have the probability that F wins Game 1 equal to Pr(G1)=Pr(G0).Game 2. C replaces the signature oracle with the signing simulator Sim. C can respond to F as follows.WhenF makes a query to Sim on message m, Sim chooses a random index r∈F2 and sets Λ(m)=r. Then, C runs H with input m. If there is no el∈εn,w, then Sim aborts; otherwise, Sim outputs el and sets Λ(m) empty.Game 2 differs from Game 1 only in the case thatSim aborts. The probability that Sim aborts is at most qSim/2n, where qSim represents the maximum query times to the Sim. It follows that the probability, denoted by Pr(G2), of F winning Game 2 satisfies (21)PrG1-PrG2≤qSim2n.Game 3. C replaces the public key (the permuted parity-check matrix of random Goppa codes) with the parity-check matrix of random linear code for each signer in this game. According to the indistinguishability assumption (see Section 2), F has only a negligible advantage Advn,k(F) in solving the GCD problem. That is, we have the probability that F wins Game 3 as |Pr(G3)-Pr(G2)|=Advn,k(F).Game 4. The wining condition is changed in this game. C picks a random number k in {1,…,qH}, where qH is the maximum query times to H. F should generate the k-th forgery message-signature pair which can pass the verification. Hence, the probability of F wining this game is Pr(G4)=Pr(G3)/qH.We remark that ifF wins Game 4, then F is able to inverse the SD problem (i.e., find a vector e′∈εn,w s.t. H′e′T=s′T). Hence, we have Pr(G4)=AdvSD(C).Combining all these together, we haveSuccF=Pr(G0) and (22)qHAdvSDC+Advn,kF≥SuccF+qSim2n. In other words, if there is a PPT forger F which can forge a valid message-signature pair with a nonnegligible probability in attacking our scheme, then we can construct a PPT algorithm C to inverse the SD problem with a nonnegligible probability. Thus, we can conclude that our proposed threshold ring signature scheme is existentially unforgeable under the chosen message attack if both the GCD problem and SD problem are hard.


## 5. Efficiency Analysis

In this section, we evaluate the efficiency of our threshold ring signature scheme, in terms of the public key size, the signature size, and the time complexity of the signing process.The Public-Key Size. As mentioned in Section 3, the ring public key in our threshold ring signature scheme is PK=(H~1,H~2,…,H~N), in which each H~i is an (n-k)×n matrix over F2, i=1,2,…,N. Hence, the ring public key PK has size n(n-k)N bits.The Signature Size. The signature in our scheme is σ=(e1,e2,…,eN), where ei∈εn,w, i=1,2,…,N. This results in a signature of size nN bits.Time Complexity of the Signing Process. We omit the consideration of computing a hash function because it is a fast operation compared to other operations involved in our (t,N) threshold ring signature scheme. As previously discussed in Section 3, each signer Si in our scheme should compute a vector si (see (8), (12), and (13)), 1≤i≤t. The time complexity of computing si is O((N-t)(n-k)n). According to Engelbert et al. [23], a fast decoding algorithm has time complexity O(n2); therefore, we should execute t! decoding algorithms on average to generate a decodable syndrome [20]. So the total time complexity of the signing process in our threshold ring signature scheme is as follows: (23)2t!ON-tn-kn+On2.Note that the time complexity of the signing process in our scheme is independent of the number of signers. The factor of the complexity of our method is two, rather thant, in comparison to the CFS scheme [20]. This is because t-1 signers (with the exception of the leader) can undertake concurrent operations in our scheme. This enables our scheme to be an efficient code-based threshold ring signature scheme.


## 6. Conclusion

In this paper, we proposed a novel threshold ring signature scheme based on the hard problems in coding theory. We prove that our method satisfies correctness, unforgeability, and anonymity. In comparison to other postquantum digital signature schemes, our scheme has a lower signature size. Our scheme also uses the leader-participant model to allow signers to sign messages concurrently. This significantly reduces the time complexity of the signing process.Future research includes exploring practical applications of the proposed scheme and implementing a prototype of the scheme for evaluation in a real-world context (e.g., in an Internet of Battlefield Things application).



---

*Source: 1915239-2017-08-01.xml*