# A Rational Threshold Signature Model and Protocol Based on Different Permissions

Authors: Bojun Wang; Cheng Cai; Quan Zhou
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

This paper develops a novel model and protocol used in some specific scenarios, in which the participants of multiple groups with different permissions can finish the signature together. We apply the secret sharing scheme based on difference equation to the private key distribution phase and secret reconstruction phrase of our threshold signature scheme. In addition, our scheme can achieve the signature success because of the punishment strategy of the repeated rational secret sharing. Besides, the bit commitment and verification method used to detect players’ cheating behavior acts as a contributing factor to prevent the internal fraud. Using bit commitments, verifiable parameters, and time sequences, this paper constructs a dynamic game model, which has the features of threshold signature management with different permissions, cheat proof, and forward security.


---

## Body

## 1. Introduction

Secret sharing (SS) scheme, first proposed by Shamir [1] in the paper “How to share a secret,” is a significant method used for the important information management. There are other SS schemes presented by Blakeley [2] and Asmuth and Bloom [3]. These (t,n)-threshold schemes above split the secret to nshares and distribute these shares to n  legal players, meaning that all the players in the secret sharing system have the same permissions. However, in some specific situations, like in a company, managers and employees are supposed to have different authority in the confidential secret management. As a result, all the SS schemes are not suitable to be applied to such scenario. Later, many scholars devoted themselves to the weighted threshold SS schemes, which can solve the above problem. Shamir was concerned with weighted threshold SS in his paper “How to share a secret”—the president of a company has three shares, the vice presidents have two shares, and others have one share. Later, Morillo et al. [4] developed some main properties related to the information ratio, which measures a secret sharing system’s security. After that, many researchers used their work to develop weight SS schemes, and some are with bipartite [5–7]. Chan and Chang [8] developed a new (t,n)-threshold scheme based on differential equations, which was completely different from the mechanism of weighted SS scheme and shared the same notion with Li [9]. Instead of the traditional weighted threshold SS schemes, which have the symmetrical permissions limitation, they proposed (t1+t2,n1+n2)-threshold SS scheme that is based on homogeneous constant coefficient linear difference equation. In the scheme, all players are divided into two groups (denoted by A, B) with the different secret management authority; just t1 players from A and t2 players from B can recover the original secret information. For example, a company divides its business secret into (n1+n2) shares, in which n1 shares are possessed by n1 specific employees and n2 shares are distributed to n2 managers. Any t1 employees and t2 managers can retrieve the business secret.Threshold signature is based on SS, which was first proposed by Desmedt and Frankel [10] and based on RSA signature mechanism. Shamir [11] introduced the concept of signature authentication based on identity. Paterson and Schuldt [12] presented efficient identity-based signatures in the standard model. In this paper, to illustrate our model, we adopt Okamoto’s signature method [13], which is based on the identification scheme and is provably secure.Another important issue about the traditional SS scheme is that they are all based on the assumption that every player is either honest or malicious. However, in practice, players are more likely to be selfish, trying to maximize their own utility. Halpern and Teague [14] introduced the notion of rational secret sharing (RSS) in 2004 and presented a randomized protocol for a t≥3,n>3 SS scheme, which can achieve Nash equilibrium after repeated elimination of weakly dominated strategy. Gordon and Katz [15] improved Halpern’s protocol to t≥2,n>2 conditions. The mechanism proposed by Maleka et al. [16] is called repeated rational secret sharing (RRSS), in which the distributor needs to do second-time segmentation of the secret shares and made the players share the subshares repeatedly. Maleka’s method uses punishment strategies to prevent players from finking, which is different from Halpern and Teague’s RSS protocol, in which some rounds of secret sharing are meaningless.In this paper, we present a rational threshold signature model, in which the participants are divided into two sets with the different permissions. We adopt the SS scheme based on the difference equations to distribute shares and recover the original secrets. In the recover phrase, players exchange their subshares repeatedly based on Maleka’s RRSS scheme. In our model, we use several modules to manage the functions, respectively. The parameter sequence generator is used to generate the parameters of the difference equations and parameter distributor is used to distribute the parameters to the participants as their shares. Rounds controller is used to generate the random number of rounds so that the players cannot know when the repeated games will end. Bit commitment module is utilized for the players to commit their own subshares and verify others’. Besides, when a player cheats in a specific round by sending the wrong subshare, the verifiable module can detect it and the protocol will be stopped so that nobody can acquire the secret.


## 2. Relative Works

### 2.1. The Model of Li Bin Scholar

The model is outlined as follows.Maker constructs homogeneous constant coefficient linear differential equation:(1)an+∑i=1t1bian-i=0(bi∈Zq),Master key:k=aN(N>n1),Shadow keys of participants in setA are (ai,b1)(i=0,1,…,n1-1),Shadow keys of participants in setB are (N,b2,…,bt1).The general term formula of homogeneous constant coefficient linear differential equation is(2)an=∑i=1t1cifi(n).Because coefficient determinant is nondegenerate second-order tensor,(3)Δt×t=|f1(0)f2(0)⋯ft(0)f1(1)f2(1)⋯ft(1)⋮⋮⋱⋮f1(t-1)f2(t-1)⋯ft(t-1)|t×t≠0.
Participants in set A calculate constant vector:
(4)c=(c1,c2,…,ct1)T.Any participant in setB makes n=N can obtain the system master key:
(5)aN=∑i=1t1cifi(N)(N>n1).


### 2.2. Problems

The model mentioned above is a big innovation in the field of threshold structure; however, if applied directly to the threshold signature, while in practical use, some problems may exist as follows.(1)
The permissions in this model have limitations. The second component of(n1+n2,t1+1)-threshold shared structure on behalf of the second category participants with special privileges; these participants have excessive permissions, because anyone of them can represent the group. Thus, weexpand the second component into (n1+n2,t1+t2) structure. Wei et al.’s scholars [17, 18] at Shandong University have proposed the definition of such structure. However, when this scheme is implemented, its two groups both use the polynomial ring, which possesses the symmetrical nature, thus it will break the different privileges characteristic of the homogeneousconstant coefficient linear differential equation. This paper promotes (n1+n2,t1+1) structure based on homogeneous constant coefficient linear differential equation, extends permissions, in the meantime, and improves the original proposal.(2)
This model cannot resist conspiracy attacks, because of that when greater than or equal to the (t1,0) threshold number of participants work out the constant vector group of equation (4), at the same time, the equation (2) is determined. Conspires can get the the private key of the participants of the first set, using the general term formula, and one copy of the private key of the second set’s participant can be used to conjecture the others’ private keys in the second set.(3)
The model cannot resist internal fraud. When put into practical use, the model does not have a verifiable, and the participants’ fraud is undetectable. If there are no validation measures, the participants may run this protocol arbitrarily, or send their false shares, and these cannot be tolerated.(4)
The model has the dealer, who is the trusted third party. In the distributed network environment, the parameters is generated by a machine or by the secure multiparty computation.(5)
This model does not have the rational characteristics. When the signature private keys are generated, and when the first set’s participants compute the equation (2)—after computing the general term formula, the participants in the second set have no motive to expose their private key to the participants in the first set, after they generate their private keys. This loses fairness.


## 2.1. The Model of Li Bin Scholar

The model is outlined as follows.Maker constructs homogeneous constant coefficient linear differential equation:(1)an+∑i=1t1bian-i=0(bi∈Zq),Master key:k=aN(N>n1),Shadow keys of participants in setA are (ai,b1)(i=0,1,…,n1-1),Shadow keys of participants in setB are (N,b2,…,bt1).The general term formula of homogeneous constant coefficient linear differential equation is(2)an=∑i=1t1cifi(n).Because coefficient determinant is nondegenerate second-order tensor,(3)Δt×t=|f1(0)f2(0)⋯ft(0)f1(1)f2(1)⋯ft(1)⋮⋮⋱⋮f1(t-1)f2(t-1)⋯ft(t-1)|t×t≠0.
Participants in set A calculate constant vector:
(4)c=(c1,c2,…,ct1)T.Any participant in setB makes n=N can obtain the system master key:
(5)aN=∑i=1t1cifi(N)(N>n1).


## 2.2. Problems

The model mentioned above is a big innovation in the field of threshold structure; however, if applied directly to the threshold signature, while in practical use, some problems may exist as follows.(1)
The permissions in this model have limitations. The second component of(n1+n2,t1+1)-threshold shared structure on behalf of the second category participants with special privileges; these participants have excessive permissions, because anyone of them can represent the group. Thus, weexpand the second component into (n1+n2,t1+t2) structure. Wei et al.’s scholars [17, 18] at Shandong University have proposed the definition of such structure. However, when this scheme is implemented, its two groups both use the polynomial ring, which possesses the symmetrical nature, thus it will break the different privileges characteristic of the homogeneousconstant coefficient linear differential equation. This paper promotes (n1+n2,t1+1) structure based on homogeneous constant coefficient linear differential equation, extends permissions, in the meantime, and improves the original proposal.(2)
This model cannot resist conspiracy attacks, because of that when greater than or equal to the (t1,0) threshold number of participants work out the constant vector group of equation (4), at the same time, the equation (2) is determined. Conspires can get the the private key of the participants of the first set, using the general term formula, and one copy of the private key of the second set’s participant can be used to conjecture the others’ private keys in the second set.(3)
The model cannot resist internal fraud. When put into practical use, the model does not have a verifiable, and the participants’ fraud is undetectable. If there are no validation measures, the participants may run this protocol arbitrarily, or send their false shares, and these cannot be tolerated.(4)
The model has the dealer, who is the trusted third party. In the distributed network environment, the parameters is generated by a machine or by the secure multiparty computation.(5)
This model does not have the rational characteristics. When the signature private keys are generated, and when the first set’s participants compute the equation (2)—after computing the general term formula, the participants in the second set have no motive to expose their private key to the participants in the first set, after they generate their private keys. This loses fairness.


## 3. Protocol Model

### 3.1. The Structure of Model

The structure of the model is shown in Figure1.Figure 1
The structure diagram of model.(
1) Parameter Sequence Generator. Each time while in the signature step, the registers in parameters sequence generator dynamically generate the next state parameters according to the last state parameters. Each signature call the module once; the use of time series technology makes the model have forward security.The initial vector in parameter sequence generator is(6)aT0=(anT0,an-1T0,…,an-t1T0)T,bT0=(b1T0,b2T0,…,bt1T0)T.The iterative formulas of parameter sequence generator are as follows:(7)aTi+1=(anρTi,an-1ρTi,…,an-t1ρTi)Tmod⁡⁡qaiaa(i≥0∧i∈Z+,ρ∈RGF(q)*),bTi+1=(b1ρTi,b2ρTi,…,bt1ρTi)Tmod⁡⁡qaia(i≥0∧i∈Z+,ρ∈RGF(q)*).Other parameters are generated like this way.Theorem 1.
The model has forward security.Proof.
On the completion of the last signature, in next signature step, the parameter sequence generator precompiled the iteration values in registers. After iteration, according to recurrence relations (7), the last data in registers will not exist. That is to say, this time’s signature data in registers will cover the last data in them. According to the recurrence relations (7), if an attacker wants to get last data in registers, he or she must calculate mode square root:
(8)akTi=akTi+1ρmod⁡q,(i≥0∧i∈Z+,k=n,…,n-t1∧ρ∈RGF(q)*),bkTi=bkTi+1ρmod⁡q,(i≥0∧i∈Z+,k=1,…,t1∧ρ∈RGF(q)*).
The mode square root in polynomial time is computationally infeasible, and the mode indices are random; attacker cannot predict. So the model has forward security.(
2) Rounds Controller. This model, which runs multiple rounds in the signature process, is a limited time repetitions dynamic game. It is vital in the model and controls the operation of the entire process. Here we use the idea of stochastic process [19] to construct model.Theorem 2.
The distribution of round obeys Poisson distribution with parameterλ.Proof.
In the condition of time limited game process, note that the number of deceptions in each round isk, with the probability satisfying the following formula:
(9)Prk(r0,r)=Pr{N(r0,r)=k}(k∈Z).
Participants’ behavior is independent in each round.
Assuming the number of rounds has continuity, that is to say, the process of game is taken as continuous function with time,(10)Pr1(r,r+Δr)=Pr{N(r,r+Δr)=1}=λΔr+o(Δr)(λ>0∧∀Δr⟶0),∑i=2∞Pri(r,r+Δr)=∑i=2∞Pr{N(r,r+Δr)=i}=o(Δr)(λ>0∧∀Δr⟶0),
and it satisfies that
(11)N(0)=0+o(ε).This means that, the probability of cracking the system withε computational advantages can be negligible, when the threshold signature process is not performed. The model satisfies the four conditions mentioned above and meets the definition of Poisson process with λ intensity. That is,
(12)N(r)-N(r0)~π(λ(r-r0)).Theorem 3.
The expectations rounds of this model areλ, each time the model convergence time complexity is O(λ).Proof.
Differential equations are established for the rounds(r0,r1,…,r*) respectively, based on the four conditions mentioned above(13)Prk(r0,r)=Pr{N(r0,r)=k}=[λ(r-r0)]kk!e-λ(r-r0)(r,k∈Z).
The mathematical expectation is(14)E[N(r)-N(r0)]=λ(r-r0).
So the expectations rounds of this model are λ, each time the model convergence time complexity is O(λ).(
3) Parameter Distributor. A machine can analog the behavior of distributor (maker) and can be a trusted server in the distributed network.(
4) Pedersen Bit Commitment Module. Pedersen bit commitment protocol [20] is a security protocol taken as commitment to the bit stream information. In each time of signature, the system generates coefficients of homogeneous constant coefficients differential equations, and the coefficients of algebraic curved F(x) with order n2-1, which correspond to the participants in set B. After storing the coefficients in the binary bits formation, we note them as form of mi(i∈Z∧mi∈{0,1}), in the form of bits stream. The parameter distributor is also attached with the bit commitment model to prevent it from attacks.Theorem 4.
The model can detect whether the parameter distributor is under attack or not.Proof.
The model adapts the Pedersen’s bit stream commitment protocol.
Parameter distributor selects a random numberρ∈RGF(pmax⁡{n1,n2})*, timestamp information t, and secure hash function H(mi,t)(i∈Z∧mi∈{0,1}).
To make bit stream and timestamp above hash process. The primitive element of groupGF(pmax⁡{n1,n2}) is g; publish
(15)δ=gρyH(mi,t)mod⁡pmax⁡⁡{n1,n2}(i∈Z∧mi∈{0,1}).
The triple (ρ,mi,t) will be publish to the public, right after the end of the signature process. Set A and set B participants can verify commitment to make sure whether parameter distributor is being attacked or not.(
5) Verifiable Parameter Distribution Module. Using the idea of Feldman’s [21] verification. First, publicize bivariate one-way function H(x,y). In each threshold signature process, parameter distributor generates polynomial with n1-1 orders which corresponds to set A participants:
(16)G(x)=∑i=1n1-1uixmod⁡pn1.Our model uses the primitive element in the finite fieldsGF(pn1), which is g1, to compute the number of the operation rounds, which is r*, according to the Poisson distribution with parameter λ, and then distribute the points sequence:
(17)(x1i,y1i)=(H(s1i,g1r*),G(x1i))(i=0,1,…,n1-1).
Then it arbitrarily selects n1-t1 points in the field of Fpn1(x,y) except the ones in the equation (17), and publish them to the public.Then it saves the vector(18)s1i(i=0,1,…,2n1-t1-1),
and calls Pedersen’s bit commitment module.After that, it broadcasts:(19)Vi=g1uimod⁡pn1(i=0,1,…,n1-1).
Send each participant in set A:
(20)TPKi=[ai+G(0)]mod⁡pn1,(i=1,2,…,n1,ai∈GF(q)*,G(0)∈GF(pn1)*>sup⁡ai).
In the set B, the parameter distributor generates the primitive element, which is g2, in the infinite field GF(pn2), according to this polynomial with n2-1 orders:
(21)L(x)=∑i=1n2-1lixmod⁡pn2.And then, with the rounds numberr* noted before, the system distributes publish the points sequence:
(22)(x2i,y2i)=(H(s2i,g2r*),L(x2i))aaaii(i=0,1,…,n2-1).
We adopt (n2,t2) threshold structure constructed by matrix method. t2 players in set B participate in the repeated games and recover the secret S using the published n2-t2 points. As a result, the players in set A can input S after they get the general term formula of homogeneous constant coefficient linear differential equation.Save vector(23)s2i(i=0,1,…,2n2-t2-1).
And call Pedersen’s bit commitment module.After that, it broadcasts:(24)Wi=g2limod⁡pn2(i=0,1,…,n2-1).Send each participant in setB:
(25)TPKj=[S+L(0)]mod⁡pn2,(j=1,2,…,n2,S∈GF(p)*,L(0)∈GF(pn2)*>S).Theorem 5.
The model is verifiable.Proof.
When distributing point’s sequence and broadcasting corresponding authentication information, participants can simultaneously verify the information.
SetA participants verify
(26)g1G(x1i)=∏j=0n1-1Vix1ijmod⁡pn1(i=0,1,…,n1-1).
SetB participants verify
(27)g2L(x2i)=∏j=0n2-1Wix2ijmod⁡pn2(i=0,1,…,n2-1).
If the verification succeeds, participants can trust the information sent by others.(
6) Participants. Participants in two different permissions together constitute the threshold structure (n1+n2,t1+t2). In addition, |A|=n1|B|=n2, and the threshold values are |A|threshold=t1 and |B|threshold=t2.(
7) Okamoto Signature Module. After calculating the threshold signature private key, take TSK=aS as the first private key component of the signature module, while the second private key component is generated by public key signature method; select private keys; and publicize public keys, respectively. The model adopts Okamoto signature algorithm to signature finally.Theorem 6.
The model can resist conspiracy attack.Proof.
The second component of the private key in Okamoto signature algorithm can avoid conspiracy attacks which are performed by using general term formula to get other participants’ private keys when meeting the threshold condition to calculate homogeneous linear differential equations with constant coefficients general term formula in original model. The second component of everyone’s private key has to be kept privately by each individual. On condition that the second component of the private key ensures the privacy, the threshold signature cannot be forged. Furthermore, we can establish a mechanism, that is when there is a dispute, the system will check every participant involving the process of signature arise disputes.


### 3.2. Improved Threshold Model

We adopt (n2, t2) threshold structure constructed by matrix method. t2 players in set B participate in the repeated games and recover the secret S using the published n2-t2 points. As a result, the players in set A can input S after they get the general term formula of homogeneous constant coefficient linear differential equation.Make two field extensions:(28)[GF(pn1):GF(q)]=[GF(pn1):GF(p)][GF(p):GF(q)],[GF(pn2):GF(q)]=[GF(pn2):GF(p)][GF(p):GF(q)].
Expansion order of algebraic number field GF(q) is
(29)Q1=[GF(pn1):GF(q)]=n1*[p-1q],Q2=[GF(pn2):GF(q)]=n2*[p-1q].Remove the noise termsL(0) and G(0) to get coefficients information of homogeneous constant coefficient linear differential equation.


### 3.3. Dynamic Game Model

Definition 7.
The Computable complete and perfect information dynamic gameτ=[P,T,A,S,R,H,I,O,U] satisfies:Participants are noted asP={Simulator,Pi}(Simulator represents the nature and parameter distributor).The set of  Types isT={Ti}(Ti∈{honesty,fraud}).Actions set isA={Ai}(Ai∈{honesty,fraud}).Strategy set isS={Si}φ:(Ti,Hi,Ii,Ai)→Si.Rounds set isR<O(λ)∧R∈Z+.Full history setH={h∣h=⨁i=1kAi}(i∈R∧0≤k≤R) is depicted as game tree, whose root is empty history node ∅.The information setI={Ii} can be tested and is perfect.Outcome set isO={Oi}γ:(Ai,Si)→Oi.Utility function set isU={Ui}γ∘φ:(Ti,Hi,Ii,Ai,Si,Oi)→Ui and satisfies ∂2Ui<0.The above gameτ can be calculated in polynomial time.Definition 8.
Computable complete and perfect information dynamic game witht1+t2 elastic equilibrium will reach the equilibrium results, under the conditions that it satisfies the Definition 7 and that each participants is rational. That is, U(σi,σ-i)<U(σi*,σ-i), σ is multiple real variable function σ:(Ti,Hi,Ii,Ai,Si,Oi,Ui)→U(σi,σ-i).Theorem 9.
The model converges to computable complete and perfect information dynamic game witht1+t2 elastic equilibrium.Proof.
Participants who accord with threshold signature conditions possess superiority ofPr=ε(0<ε<1). They can get threshold signature private key without the normal operation of the model. Definitions of utility functions are as follows:
U
(
0
,
i
)
+
+: participants’ ideal utility without the normal operation of the model to obtain the threshold signature private key;
U
(
r
,
i
)
+
(
0
≤
r
≤
r
*
): the utility that participant i gets signature private key and others do not get it in r round;
U
(
r
,
i
)
-
(
0
≤
r
≤
r
*
): utility that participant i does not comply with the normal execution of the model when model run r round;
U
(
r
,
i
)
(
0
≤
r
≤
r
*
): utility that participant i complies with the normal execution of the model when model run r round;
U
(
r
*
,
i
): normal utility that participant i always complies with the operation of the model obtains threshold signature private key when model reaches the last one round;
U
(
r
,
all
)
-
(
0
≤
r
≤
r
*
): utility that all participants do not obtain the threshold signature private key. Illustrate that there are some participants had deceived cause model abnormal termination.
Utility function satisfies the strong partial:U(0,i)++>U(r,i)+>U(r*,i)>U(r,all)-.
Define events as follows.A: participant uses the advantage ofPr=ε(0<ε<1) to crack threshold signature private key.B: participant implements protocol.C: participant takes honesty policy in roundr.D: participant takes fraud policy in roundr.We denote the utility of departing from the protocol as Uexception and denote the expected utility as E(Uexception). We can get the equation as follows. 									(30)Uexception=εU(Pr(A))+(1-ε)U(Pr(B)),U(Pr(B))=U(Pr(B∣C)Pr⁡(C)+Pr(B∣D)Pr⁡(D))=λU(r*,i)+(1-λ)∑i=1rU(r,i)-=λU(r*,i)+(1-λ)×∑i=1r[(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaa+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-],Uexception=εU(0,i)+++(1-ε)×[+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-(GF(p)*-1)2|GF(p)*||GF(p)*|U(r*,i)+(1-λ)aaaaiaai×∑i=1r((GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaaaaaai+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-)],[GF(p):GF(q)]=p-1q.
In our protocol,
(31)Uexception<U(r*,i).
Distribution function satisfies(32)r*=ψ(λ).
The following formulas are met:(33)λ<Φ*[+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-U(r*,i)-εU(0,i)++1-εaaaaaiaaa-∑i=1r(+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaaaaiaai+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-)],
in which
(34)Φ=1×(U(r*,i)-∑i=1r(+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaaaaaaaaiaiai+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-))-1.
The above equation can determine the range of parameters selection, so that the model converges to computable complete and perfect information dynamic game witht1+t2 elastic equilibrium.Theorem 10.
The model can resist inner fraud.Proof.
According to Theorem 9, a rational participant will not depart from the protocol execution in any round. The model overcomes the sensitivity of backward induction and adopts mixed strategy equilibrium. If participants adopted a deceptive strategy in the model execution of any round, this caused the decrease in revenue of participants toU(r,all)-. When the protocol terminates, punishment strategies can be used, thus putting an end to deceiving behavior effectively. So the model can prevent inner fraud.


## 3.1. The Structure of Model

The structure of the model is shown in Figure1.Figure 1
The structure diagram of model.(
1) Parameter Sequence Generator. Each time while in the signature step, the registers in parameters sequence generator dynamically generate the next state parameters according to the last state parameters. Each signature call the module once; the use of time series technology makes the model have forward security.The initial vector in parameter sequence generator is(6)aT0=(anT0,an-1T0,…,an-t1T0)T,bT0=(b1T0,b2T0,…,bt1T0)T.The iterative formulas of parameter sequence generator are as follows:(7)aTi+1=(anρTi,an-1ρTi,…,an-t1ρTi)Tmod⁡⁡qaiaa(i≥0∧i∈Z+,ρ∈RGF(q)*),bTi+1=(b1ρTi,b2ρTi,…,bt1ρTi)Tmod⁡⁡qaia(i≥0∧i∈Z+,ρ∈RGF(q)*).Other parameters are generated like this way.Theorem 1.
The model has forward security.Proof.
On the completion of the last signature, in next signature step, the parameter sequence generator precompiled the iteration values in registers. After iteration, according to recurrence relations (7), the last data in registers will not exist. That is to say, this time’s signature data in registers will cover the last data in them. According to the recurrence relations (7), if an attacker wants to get last data in registers, he or she must calculate mode square root:
(8)akTi=akTi+1ρmod⁡q,(i≥0∧i∈Z+,k=n,…,n-t1∧ρ∈RGF(q)*),bkTi=bkTi+1ρmod⁡q,(i≥0∧i∈Z+,k=1,…,t1∧ρ∈RGF(q)*).
The mode square root in polynomial time is computationally infeasible, and the mode indices are random; attacker cannot predict. So the model has forward security.(
2) Rounds Controller. This model, which runs multiple rounds in the signature process, is a limited time repetitions dynamic game. It is vital in the model and controls the operation of the entire process. Here we use the idea of stochastic process [19] to construct model.Theorem 2.
The distribution of round obeys Poisson distribution with parameterλ.Proof.
In the condition of time limited game process, note that the number of deceptions in each round isk, with the probability satisfying the following formula:
(9)Prk(r0,r)=Pr{N(r0,r)=k}(k∈Z).
Participants’ behavior is independent in each round.
Assuming the number of rounds has continuity, that is to say, the process of game is taken as continuous function with time,(10)Pr1(r,r+Δr)=Pr{N(r,r+Δr)=1}=λΔr+o(Δr)(λ>0∧∀Δr⟶0),∑i=2∞Pri(r,r+Δr)=∑i=2∞Pr{N(r,r+Δr)=i}=o(Δr)(λ>0∧∀Δr⟶0),
and it satisfies that
(11)N(0)=0+o(ε).This means that, the probability of cracking the system withε computational advantages can be negligible, when the threshold signature process is not performed. The model satisfies the four conditions mentioned above and meets the definition of Poisson process with λ intensity. That is,
(12)N(r)-N(r0)~π(λ(r-r0)).Theorem 3.
The expectations rounds of this model areλ, each time the model convergence time complexity is O(λ).Proof.
Differential equations are established for the rounds(r0,r1,…,r*) respectively, based on the four conditions mentioned above(13)Prk(r0,r)=Pr{N(r0,r)=k}=[λ(r-r0)]kk!e-λ(r-r0)(r,k∈Z).
The mathematical expectation is(14)E[N(r)-N(r0)]=λ(r-r0).
So the expectations rounds of this model are λ, each time the model convergence time complexity is O(λ).(
3) Parameter Distributor. A machine can analog the behavior of distributor (maker) and can be a trusted server in the distributed network.(
4) Pedersen Bit Commitment Module. Pedersen bit commitment protocol [20] is a security protocol taken as commitment to the bit stream information. In each time of signature, the system generates coefficients of homogeneous constant coefficients differential equations, and the coefficients of algebraic curved F(x) with order n2-1, which correspond to the participants in set B. After storing the coefficients in the binary bits formation, we note them as form of mi(i∈Z∧mi∈{0,1}), in the form of bits stream. The parameter distributor is also attached with the bit commitment model to prevent it from attacks.Theorem 4.
The model can detect whether the parameter distributor is under attack or not.Proof.
The model adapts the Pedersen’s bit stream commitment protocol.
Parameter distributor selects a random numberρ∈RGF(pmax⁡{n1,n2})*, timestamp information t, and secure hash function H(mi,t)(i∈Z∧mi∈{0,1}).
To make bit stream and timestamp above hash process. The primitive element of groupGF(pmax⁡{n1,n2}) is g; publish
(15)δ=gρyH(mi,t)mod⁡pmax⁡⁡{n1,n2}(i∈Z∧mi∈{0,1}).
The triple (ρ,mi,t) will be publish to the public, right after the end of the signature process. Set A and set B participants can verify commitment to make sure whether parameter distributor is being attacked or not.(
5) Verifiable Parameter Distribution Module. Using the idea of Feldman’s [21] verification. First, publicize bivariate one-way function H(x,y). In each threshold signature process, parameter distributor generates polynomial with n1-1 orders which corresponds to set A participants:
(16)G(x)=∑i=1n1-1uixmod⁡pn1.Our model uses the primitive element in the finite fieldsGF(pn1), which is g1, to compute the number of the operation rounds, which is r*, according to the Poisson distribution with parameter λ, and then distribute the points sequence:
(17)(x1i,y1i)=(H(s1i,g1r*),G(x1i))(i=0,1,…,n1-1).
Then it arbitrarily selects n1-t1 points in the field of Fpn1(x,y) except the ones in the equation (17), and publish them to the public.Then it saves the vector(18)s1i(i=0,1,…,2n1-t1-1),
and calls Pedersen’s bit commitment module.After that, it broadcasts:(19)Vi=g1uimod⁡pn1(i=0,1,…,n1-1).
Send each participant in set A:
(20)TPKi=[ai+G(0)]mod⁡pn1,(i=1,2,…,n1,ai∈GF(q)*,G(0)∈GF(pn1)*>sup⁡ai).
In the set B, the parameter distributor generates the primitive element, which is g2, in the infinite field GF(pn2), according to this polynomial with n2-1 orders:
(21)L(x)=∑i=1n2-1lixmod⁡pn2.And then, with the rounds numberr* noted before, the system distributes publish the points sequence:
(22)(x2i,y2i)=(H(s2i,g2r*),L(x2i))aaaii(i=0,1,…,n2-1).
We adopt (n2,t2) threshold structure constructed by matrix method. t2 players in set B participate in the repeated games and recover the secret S using the published n2-t2 points. As a result, the players in set A can input S after they get the general term formula of homogeneous constant coefficient linear differential equation.Save vector(23)s2i(i=0,1,…,2n2-t2-1).
And call Pedersen’s bit commitment module.After that, it broadcasts:(24)Wi=g2limod⁡pn2(i=0,1,…,n2-1).Send each participant in setB:
(25)TPKj=[S+L(0)]mod⁡pn2,(j=1,2,…,n2,S∈GF(p)*,L(0)∈GF(pn2)*>S).Theorem 5.
The model is verifiable.Proof.
When distributing point’s sequence and broadcasting corresponding authentication information, participants can simultaneously verify the information.
SetA participants verify
(26)g1G(x1i)=∏j=0n1-1Vix1ijmod⁡pn1(i=0,1,…,n1-1).
SetB participants verify
(27)g2L(x2i)=∏j=0n2-1Wix2ijmod⁡pn2(i=0,1,…,n2-1).
If the verification succeeds, participants can trust the information sent by others.(
6) Participants. Participants in two different permissions together constitute the threshold structure (n1+n2,t1+t2). In addition, |A|=n1|B|=n2, and the threshold values are |A|threshold=t1 and |B|threshold=t2.(
7) Okamoto Signature Module. After calculating the threshold signature private key, take TSK=aS as the first private key component of the signature module, while the second private key component is generated by public key signature method; select private keys; and publicize public keys, respectively. The model adopts Okamoto signature algorithm to signature finally.Theorem 6.
The model can resist conspiracy attack.Proof.
The second component of the private key in Okamoto signature algorithm can avoid conspiracy attacks which are performed by using general term formula to get other participants’ private keys when meeting the threshold condition to calculate homogeneous linear differential equations with constant coefficients general term formula in original model. The second component of everyone’s private key has to be kept privately by each individual. On condition that the second component of the private key ensures the privacy, the threshold signature cannot be forged. Furthermore, we can establish a mechanism, that is when there is a dispute, the system will check every participant involving the process of signature arise disputes.


## 3.2. Improved Threshold Model

We adopt (n2, t2) threshold structure constructed by matrix method. t2 players in set B participate in the repeated games and recover the secret S using the published n2-t2 points. As a result, the players in set A can input S after they get the general term formula of homogeneous constant coefficient linear differential equation.Make two field extensions:(28)[GF(pn1):GF(q)]=[GF(pn1):GF(p)][GF(p):GF(q)],[GF(pn2):GF(q)]=[GF(pn2):GF(p)][GF(p):GF(q)].
Expansion order of algebraic number field GF(q) is
(29)Q1=[GF(pn1):GF(q)]=n1*[p-1q],Q2=[GF(pn2):GF(q)]=n2*[p-1q].Remove the noise termsL(0) and G(0) to get coefficients information of homogeneous constant coefficient linear differential equation.


## 3.3. Dynamic Game Model

Definition 7.
The Computable complete and perfect information dynamic gameτ=[P,T,A,S,R,H,I,O,U] satisfies:Participants are noted asP={Simulator,Pi}(Simulator represents the nature and parameter distributor).The set of  Types isT={Ti}(Ti∈{honesty,fraud}).Actions set isA={Ai}(Ai∈{honesty,fraud}).Strategy set isS={Si}φ:(Ti,Hi,Ii,Ai)→Si.Rounds set isR<O(λ)∧R∈Z+.Full history setH={h∣h=⨁i=1kAi}(i∈R∧0≤k≤R) is depicted as game tree, whose root is empty history node ∅.The information setI={Ii} can be tested and is perfect.Outcome set isO={Oi}γ:(Ai,Si)→Oi.Utility function set isU={Ui}γ∘φ:(Ti,Hi,Ii,Ai,Si,Oi)→Ui and satisfies ∂2Ui<0.The above gameτ can be calculated in polynomial time.Definition 8.
Computable complete and perfect information dynamic game witht1+t2 elastic equilibrium will reach the equilibrium results, under the conditions that it satisfies the Definition 7 and that each participants is rational. That is, U(σi,σ-i)<U(σi*,σ-i), σ is multiple real variable function σ:(Ti,Hi,Ii,Ai,Si,Oi,Ui)→U(σi,σ-i).Theorem 9.
The model converges to computable complete and perfect information dynamic game witht1+t2 elastic equilibrium.Proof.
Participants who accord with threshold signature conditions possess superiority ofPr=ε(0<ε<1). They can get threshold signature private key without the normal operation of the model. Definitions of utility functions are as follows:
U
(
0
,
i
)
+
+: participants’ ideal utility without the normal operation of the model to obtain the threshold signature private key;
U
(
r
,
i
)
+
(
0
≤
r
≤
r
*
): the utility that participant i gets signature private key and others do not get it in r round;
U
(
r
,
i
)
-
(
0
≤
r
≤
r
*
): utility that participant i does not comply with the normal execution of the model when model run r round;
U
(
r
,
i
)
(
0
≤
r
≤
r
*
): utility that participant i complies with the normal execution of the model when model run r round;
U
(
r
*
,
i
): normal utility that participant i always complies with the operation of the model obtains threshold signature private key when model reaches the last one round;
U
(
r
,
all
)
-
(
0
≤
r
≤
r
*
): utility that all participants do not obtain the threshold signature private key. Illustrate that there are some participants had deceived cause model abnormal termination.
Utility function satisfies the strong partial:U(0,i)++>U(r,i)+>U(r*,i)>U(r,all)-.
Define events as follows.A: participant uses the advantage ofPr=ε(0<ε<1) to crack threshold signature private key.B: participant implements protocol.C: participant takes honesty policy in roundr.D: participant takes fraud policy in roundr.We denote the utility of departing from the protocol as Uexception and denote the expected utility as E(Uexception). We can get the equation as follows. 									(30)Uexception=εU(Pr(A))+(1-ε)U(Pr(B)),U(Pr(B))=U(Pr(B∣C)Pr⁡(C)+Pr(B∣D)Pr⁡(D))=λU(r*,i)+(1-λ)∑i=1rU(r,i)-=λU(r*,i)+(1-λ)×∑i=1r[(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaa+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-],Uexception=εU(0,i)+++(1-ε)×[+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-(GF(p)*-1)2|GF(p)*||GF(p)*|U(r*,i)+(1-λ)aaaaiaai×∑i=1r((GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaaaaaai+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-)],[GF(p):GF(q)]=p-1q.
In our protocol,
(31)Uexception<U(r*,i).
Distribution function satisfies(32)r*=ψ(λ).
The following formulas are met:(33)λ<Φ*[+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-U(r*,i)-εU(0,i)++1-εaaaaaiaaa-∑i=1r(+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaaaaiaai+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-)],
in which
(34)Φ=1×(U(r*,i)-∑i=1r(+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-1|GF(p)*||GF(p)*|U(r,i)+aaaaaaaaaaaaaaiaiai+(GF(p)*-1)2|GF(p)*||GF(p)*|U(r,all)-))-1.
The above equation can determine the range of parameters selection, so that the model converges to computable complete and perfect information dynamic game witht1+t2 elastic equilibrium.Theorem 10.
The model can resist inner fraud.Proof.
According to Theorem 9, a rational participant will not depart from the protocol execution in any round. The model overcomes the sensitivity of backward induction and adopts mixed strategy equilibrium. If participants adopted a deceptive strategy in the model execution of any round, this caused the decrease in revenue of participants toU(r,all)-. When the protocol terminates, punishment strategies can be used, thus putting an end to deceiving behavior effectively. So the model can prevent inner fraud.


## 4. Protocol Procedure

### 4.1. Parameters Generation Process

Determine the order of setA and set B; determine the threshold value according to the requirements, respectively. Select big prime q,p meets q∣(p-1). Select primitive element g1 in finite field GF(pn1) and g2 in finite field GF(pn2). The participants in set A and set B select signature private key as the second component of the Okamoto signature, respectively.Parameter sequence generator generates coefficient constants vector of homogeneous constant coefficient linear differential equation:(35)a0=(a10,a20,…,an-t10)(ai0∈Zq),b0=(b10,b20,…,bn-t10)(bi0∈Zq).Superscript represents signature number of times; 0 represents the first signature.


### 4.2. Dynamic Games Process

Rounds controller according to Poisson distribution with parameterλ secret generates threshold signature round r*. According to the number of participants in set A and set B, the threshold value generates coefficient constants vector of polynomial G(x) and L(x), respectively:
(36)u0=(u10,u20,…,un10)(ui0∈Zqn1),l0=(l10,l20,…,ln20)(li0∈Zqn2).Superscript signature represents the number of rounds; 0 represents the first round.Parameter distributor according to (17) and (22) distributes and publicizes points. Participants in set A and set B can use the verifiable parameter distribution module for verification. If there is no cheating behavior, the protocol continues to execute. Otherwise, the verifiable parameter distribution module goes to the interrupt processing. In every round of the games, the players in set A and set B use the published points sequence and generate G(0)r and L(0)r, respectively.Parameter distributor verifies, respectively,(37)[TPKi-Gr(0)]mod⁡pn1=?ai,(Gr(0)∈GF(pn1)*>sup⁡ai,i=1,2,…,n1),[TPKj-Lr(0)]mod⁡pn2=?S,(S∈GF(p)*∧Lr(0)∈GF(pn2)*>S,j=1,2,…,n2).Ifr=r*and (37) holds, calculate (2), and then
(38)TSK=aS(S>n1+n2).Ifr≠r* and (37) does not hold, G(0)rand Lr(0) equal the expected value and the protocol enters into the next round.Ifr≠r* and (37) does not hold, meanwhile, G(0)r and Lr(0) do not equal the expected value, someone of the players have cheated. At this time, the parameter distributor can perceive the cheating behavior so that the player cannot obtain the signature private key. According to Theorem 10, the rational participants will not deceive.


### 4.3. Threshold Signature Process

The Okamoto signature module is used to complete the feature of signature.Okamoto signature algorithm contains two private keys: the first is threshold signature private key just generated, and the second is each participator’s signature private key in setA and set B. Only after verification, parameter distributor can call Okamoto signature module. Two private key generation equations are as follows:
(39)TSK1=aS(S>n1+n2),TSK2=∏i=0t1+t2-1SHA(m)SKi.
Verify equation
(40)∏i=0t1+t2-1TSK2PKi=?SHA(m).m is message sequence, and SHA is secure hash function.We use the equation (41) to complete signature
(41)(σ1,σ2,σ3)=Okamoto(TSK1,TSK2).Validation process can use standard Okamoto algorithm.


### 4.4. Several Models Comparison

Table1 is several models comparison. The parameters range of this model uses the limiting form of (31), (32), (33), and (34).Table 1
Several models comparison.
Model
Verifiable
Bit Commitment
Resists conspiracy attack
Forward security
Permission
Convergence time
Range of parameters
Halpern and Teague
No
No
No
No
Different
O
(
5
α
3
)
(
0
<
α
<
1
)
α
2
α
2
+
(
1
-
α
)
2
U
+
(
σ
i
,
σ
-
i
)
+
(
1
-
α
)
2
α
2
+
(
1
-
α
)
2
U
-
(
σ
i
,
σ
-
i
)
>
U
(
σ
i
*
,
σ
-
i
)
Gordon and Katz
No
No
No
No
Different
O
(
1
β
)
(
0
<
β
<
1
)
β
≤
U
(
σ
i
*
,
σ
-
i
)
-
U
-
(
σ
i
,
σ
-
i
)
U
+
(
σ
i
,
σ
-
i
)
-
U
-
(
σ
i
,
σ
-
i
)
Computable complete and perfect information dynamic game
Yes
Yes
Yes
Yes
Different
O
(
λ
)
(
λ
>
0
)
λ
<
U
(
r
*
,
i
)
-
ε
U
(
0
,
i
)
+
+
(
1
-
ε
)
*
U
(
r
*
,
i
)


## 4.1. Parameters Generation Process

Determine the order of setA and set B; determine the threshold value according to the requirements, respectively. Select big prime q,p meets q∣(p-1). Select primitive element g1 in finite field GF(pn1) and g2 in finite field GF(pn2). The participants in set A and set B select signature private key as the second component of the Okamoto signature, respectively.Parameter sequence generator generates coefficient constants vector of homogeneous constant coefficient linear differential equation:(35)a0=(a10,a20,…,an-t10)(ai0∈Zq),b0=(b10,b20,…,bn-t10)(bi0∈Zq).Superscript represents signature number of times; 0 represents the first signature.


## 4.2. Dynamic Games Process

Rounds controller according to Poisson distribution with parameterλ secret generates threshold signature round r*. According to the number of participants in set A and set B, the threshold value generates coefficient constants vector of polynomial G(x) and L(x), respectively:
(36)u0=(u10,u20,…,un10)(ui0∈Zqn1),l0=(l10,l20,…,ln20)(li0∈Zqn2).Superscript signature represents the number of rounds; 0 represents the first round.Parameter distributor according to (17) and (22) distributes and publicizes points. Participants in set A and set B can use the verifiable parameter distribution module for verification. If there is no cheating behavior, the protocol continues to execute. Otherwise, the verifiable parameter distribution module goes to the interrupt processing. In every round of the games, the players in set A and set B use the published points sequence and generate G(0)r and L(0)r, respectively.Parameter distributor verifies, respectively,(37)[TPKi-Gr(0)]mod⁡pn1=?ai,(Gr(0)∈GF(pn1)*>sup⁡ai,i=1,2,…,n1),[TPKj-Lr(0)]mod⁡pn2=?S,(S∈GF(p)*∧Lr(0)∈GF(pn2)*>S,j=1,2,…,n2).Ifr=r*and (37) holds, calculate (2), and then
(38)TSK=aS(S>n1+n2).Ifr≠r* and (37) does not hold, G(0)rand Lr(0) equal the expected value and the protocol enters into the next round.Ifr≠r* and (37) does not hold, meanwhile, G(0)r and Lr(0) do not equal the expected value, someone of the players have cheated. At this time, the parameter distributor can perceive the cheating behavior so that the player cannot obtain the signature private key. According to Theorem 10, the rational participants will not deceive.


## 4.3. Threshold Signature Process

The Okamoto signature module is used to complete the feature of signature.Okamoto signature algorithm contains two private keys: the first is threshold signature private key just generated, and the second is each participator’s signature private key in setA and set B. Only after verification, parameter distributor can call Okamoto signature module. Two private key generation equations are as follows:
(39)TSK1=aS(S>n1+n2),TSK2=∏i=0t1+t2-1SHA(m)SKi.
Verify equation
(40)∏i=0t1+t2-1TSK2PKi=?SHA(m).m is message sequence, and SHA is secure hash function.We use the equation (41) to complete signature
(41)(σ1,σ2,σ3)=Okamoto(TSK1,TSK2).Validation process can use standard Okamoto algorithm.


## 4.4. Several Models Comparison

Table1 is several models comparison. The parameters range of this model uses the limiting form of (31), (32), (33), and (34).Table 1
Several models comparison.
Model
Verifiable
Bit Commitment
Resists conspiracy attack
Forward security
Permission
Convergence time
Range of parameters
Halpern and Teague
No
No
No
No
Different
O
(
5
α
3
)
(
0
<
α
<
1
)
α
2
α
2
+
(
1
-
α
)
2
U
+
(
σ
i
,
σ
-
i
)
+
(
1
-
α
)
2
α
2
+
(
1
-
α
)
2
U
-
(
σ
i
,
σ
-
i
)
>
U
(
σ
i
*
,
σ
-
i
)
Gordon and Katz
No
No
No
No
Different
O
(
1
β
)
(
0
<
β
<
1
)
β
≤
U
(
σ
i
*
,
σ
-
i
)
-
U
-
(
σ
i
,
σ
-
i
)
U
+
(
σ
i
,
σ
-
i
)
-
U
-
(
σ
i
,
σ
-
i
)
Computable complete and perfect information dynamic game
Yes
Yes
Yes
Yes
Different
O
(
λ
)
(
λ
>
0
)
λ
<
U
(
r
*
,
i
)
-
ε
U
(
0
,
i
)
+
+
(
1
-
ε
)
*
U
(
r
*
,
i
)


## 5. Conclusion

This paper proposed computable complete and perfect information dynamic game witht1+t2 elastic equilibrium, based on the homogeneous constant coefficient linear differential equation. We constructs a dynamic game model and protocol using time sequences, bit commitments, Feldman’s verification menthod, and Okamoto’s signature permissions. The model achieves two different threshold signature permissions. We proved that, during the game, no participant has the tendency of departing from normal operation, so that the model achieves the purpose of preventing fraud. Our method expands the idea of permission and overcomes five inherent problems in homogeneous constant coefficient linear differential equation.



---

*Source: 176085-2014-07-23.xml*