# A Fully Adaptively Secure Threshold Signature Scheme Based on Dual-Form Signatures Technology

Authors: Yuanju Gan
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Int,n threshold signature schemes, any subset of t participants out of n can produce a valid signature, but any fewer than t participants cannot. Meanwhile, a threshold signature scheme should remain robust and unforgeable against up to t−1 corrupted participants. This nonforgeability property is that even an adversary breaking into up to t−1 participants should be unable to generate signatures on its own. Existential unforgeability against adaptive chosen message attacks is widely considered as a standard security notion for digital signature, and threshold signature should also follow this accordingly. However, there are two special attack models in a threshold signature scheme: one is the static corruption attack and the other is the adaptive corruption attack. Since the adaptive corruption model appears to better capture real threats, designing and proving threshold signature schemes secure in the adaptive corruption model has been focused on in recent years. If a threshold signature is secure under adaptive chosen message attack and adaptive corruption attack, we say it is fully adaptively secure. In this paper, based on the dual pairing vector spaces technology, we construct a threshold signature scheme and use Gerbush et al.’s dual-form signatures technology to prove our scheme, which is fully adaptively secure in the standard model, and then compare it to other schemes in terms of the efficiency and computation.


---

## Body

## 1. Introduction

A simple communication model, in which there is a single pair, sender and receiver, has to be extended by allowing communication between groups. To meet the security requirements for such a model, group-oriented cryptography was invented by Desmedt [1]. Given a group of n participants. A t,n threshold signature is a cryptographic protocol that allows any subgroup of t participants t≤n to collectively sign messages. On the other hand, any subgroup of t−1 participants (or smaller) is unable to generate a valid signature for any message. A threshold signature is called robust if misbehaving participants (who do not follow the protocol) are unable to prevent the honest participants from a successful execution of the signature protocol.Goldwasser et al. studied the security of signatures in [2]. They introduced a security notion called existential unforgeability against chosen message attacks (EUF-CMA) and analysed it using an appropriate security game. In the game, an adversary can get a public key (for signature verification) and she can query a signature oracle a polynomial number of times for messages of her choice. She wins the game (and breaks the security) if she is able to come up with a valid signature σ∗ for a message m∗ that has not been queried before. There are two flavours of the game: nonadaptive and adaptive. In a nonadaptive EUF-CMA, the adversary queries the signature oracle before she gets the public key. In an adaptive EUF-CMA, she gets the public key first and then she uses the signature oracle.In group-oriented cryptography, there are two basic adversarial models: static and adaptive. In the static model, the adversary fixes a subset of participants that she wants to corrupt before the protocol starts [3, 4]. In the adaptive model, the adversary waits for an appropriate time during the protocol execution. She collects information from a protocol run and corrupts a specific subset of participants to maximise her chances of success [5–7]. Clearly, the adaptive adversary is strictly stronger than the static one. Besides, the adaptive model reflects better real-life adversaries and therefore it has attracted more attention from researchers. Needless to say, it is a more challenging task to design threshold signatures with EUF-aCMA security under the adaptive adversarial model (than under the static model).In 2004, Abe and Fehr in their work [8] proposed threshold signatures secure against adaptive corruptions using the universal composability framework. Although reduced, there is still a need for interactions. Wang et al. [7] apply the Waters signatures [9] to construct threshold signatures secure against adaptive adversaries in the standard model. Their signatures still require interactions via secure point-to-point channels.Libert and Yung [10] used the Lewko-Waters identity-based encryption [11] and bilinear mapping over groups of composite order to design threshold signatures secure against adaptive adversaries, where there is no need for interactions. However, Freeman [12] argued that, for the same security level, the Libert-Yung signatures are roughly 50 times slower than signatures in prime-order groups. Hwang et al. in their work [13] constructed t,n threshold directed signatures that are existentially unforgeable under the chosen message attack under the assumption that the computational Diffie-Hellman problem is intractable. However, the security claims hold only when the adversary is static. Raman et al. in their work [14] proposed threshold proxy signatures based on the RSA assumptions. Both constructions [13, 14] are not secure against adaptive corruptions.Libert et al. [15] employ the Pedersen distributed key generation protocol [16] to design two variants of threshold signatures that are adaptively secure against a static adversary. The efficiency of the first scheme is high, but the security proof is done in the random-oracle model. The second scheme is proven secure in the standard model using the Groth-Sahai arguments [17]. Unfortunately, the time price is low efficiency; for example, the time required for a partial signature is proportional to the length of the block message. Harn and Wang [18] have studied threshold signatures using the Chinese remainder theorem. Their designs are secure against adaptively chosen message attacks and static corruptions in the random-oracle model. Recently, Assidi et al. [19] have proposed an efficient code-based threshold ring signature. However, their scheme cannot withstand the adaptive corruptions attacks.It turns out that the dual pairing vector space (DPVS) technique offers a powerful tool for constructing cryptographic algorithms such as identity-based encryption (IBE) and attribute-based encryption (ABE). We show that the technique can also be employed to design threshold signatures. The main contribution of our paper is the construction oft,n threshold signatures that are EUF-CMA secure under adaptive corruption attacks in the standard model. Our construction is based on the Lewko identity-based encryption [20] and the Okamoto-Takashima DPVS technique [21, 22]. The security proof, however, applies dual-form signature arguments developed by Gerbush et al. in [23].


## 2. Preliminaries

Given a setS. We denote by x←RS the fact that x is drawn randomly and uniformly from S. S denotes the set cardinality and x is the length of x (or the number of bits in its binary form). If ℕ is the set of natural numbers, then 1k denotes the string of k ones; k∈ℕ.


### 2.1. Bilinear Maps

Given two cyclic groupsG and GT of prime order p, a bilinear map e⋅,⋅ is a function G×G⟶GT such that, for any generator g∈G and any integers α,β∈ℤp , the map satisfies the following properties [24]:(i)
Bilinearity:egα,gβ=eg,gαβ(ii)
Nondegeneracy:eg,g≠1GT unless g=1G(iii)
Computability: there exists an efficient algorithm that computeseg1,g2 for ∀g1,g2∈GNote thatℤp is the set of integers modulo p. Let us introduce the notation that will be used in the paper. Given a vector w=w1,…,wℓ∈ℤpℓ and an integer a∈ℤp, we define the following shorthand notations:(i)
gw=gw1,…,gwℓ, where g∈G(ii)
wa=w1a,…,wℓa(iii)
gw1gw2⋯gwn=gw1+w2+⋯+wn, where wi∈ℤpℓ for i=1,2,…,n and g∈G(iv)
∏i=1nwi=∏i=1nwi,1,∏i=1nwi,2,…,∏i=1nwi,ℓ, where wi=wi,1,wi,2,…,wi,ℓ∈ℤpℓ(v)
eℓgv,gw=∏i=1ℓegvi,gwi=eg,gv,w, where v,w∈ℤpℓ, e is a bilinear map and g∈GA group generation algorithmGGΛ takes a requested security level parameter Λ and returns G,GT,p,e⋅,⋅,g, where p is a large prime and g is a generator of G.


### 2.2. Dual Pairing Vector Spaces

Given two random basesB=b1,…,bℓ and B∗=b1∗,…,bℓ∗ over ℤpℓ, the bases B and B∗ are called dual orthonormal if bi,bj∗=0 when i≠j and bi,bi∗=ψ when i=1,2,…,ℓ, where ψ∈ℤp. Note that, for a generator g of G, the following relation holds:(1)eℓgbi,gbj∗=1GT,as long asi≠j.Dualℤpℓ denotes the set of dual orthonormal bases [20, 21, 25].


### 2.3. Subspace Intractability Assumption

Given a group generatorGGΛ and a positive integer k≤ℓ/3, the subspace assumption is defined as follows [20]. For a given security level Λ, generate the parameters of an instance at random:(2)G,GT,p,e⋅,⋅,g←RGGΛ,B,B∗←RDualℤpℓ,η,β,τ1,τ2,τ3,μ1,μ2,μ3←Rℤp.Calculate the following collection of vectors:(3)Ui=gμ1bi+μ2bk+i+μ3b2k+i,Vi=gτ1ηbi∗+τ2βbk+i∗,Wi=gτ1ηbi∗+τ2βbk+i∗+τ3b2k+i∗,where i=1,2,…,k. Then calculate a vector D such that(4)D=G,GT,p,e⋅,⋅,g,gb1,gb2,…,gb2k,gb3k+1,…,gbℓ,gηb1∗,…,gηbk∗,gβbk+1∗,…,gβb2k∗,gb2k+1∗,…,gbℓ∗,U1,U2,…,Uk,μ3.We assume that, for any probabilistic polynomial time (PPT) algorithmA, the advantage in distinguishing vectors Vi from vectors Wi, where i=1,2,…,k, is negligible in the security parameter Λ or(5)ADVGG,AΛ=PAD,V1,…,Vk=1−PAD,W1,…,Wk=1<1polyΛ.


## 2.1. Bilinear Maps

Given two cyclic groupsG and GT of prime order p, a bilinear map e⋅,⋅ is a function G×G⟶GT such that, for any generator g∈G and any integers α,β∈ℤp , the map satisfies the following properties [24]:(i)
Bilinearity:egα,gβ=eg,gαβ(ii)
Nondegeneracy:eg,g≠1GT unless g=1G(iii)
Computability: there exists an efficient algorithm that computeseg1,g2 for ∀g1,g2∈GNote thatℤp is the set of integers modulo p. Let us introduce the notation that will be used in the paper. Given a vector w=w1,…,wℓ∈ℤpℓ and an integer a∈ℤp, we define the following shorthand notations:(i)
gw=gw1,…,gwℓ, where g∈G(ii)
wa=w1a,…,wℓa(iii)
gw1gw2⋯gwn=gw1+w2+⋯+wn, where wi∈ℤpℓ for i=1,2,…,n and g∈G(iv)
∏i=1nwi=∏i=1nwi,1,∏i=1nwi,2,…,∏i=1nwi,ℓ, where wi=wi,1,wi,2,…,wi,ℓ∈ℤpℓ(v)
eℓgv,gw=∏i=1ℓegvi,gwi=eg,gv,w, where v,w∈ℤpℓ, e is a bilinear map and g∈GA group generation algorithmGGΛ takes a requested security level parameter Λ and returns G,GT,p,e⋅,⋅,g, where p is a large prime and g is a generator of G.


## 2.2. Dual Pairing Vector Spaces

Given two random basesB=b1,…,bℓ and B∗=b1∗,…,bℓ∗ over ℤpℓ, the bases B and B∗ are called dual orthonormal if bi,bj∗=0 when i≠j and bi,bi∗=ψ when i=1,2,…,ℓ, where ψ∈ℤp. Note that, for a generator g of G, the following relation holds:(1)eℓgbi,gbj∗=1GT,as long asi≠j.Dualℤpℓ denotes the set of dual orthonormal bases [20, 21, 25].


## 2.3. Subspace Intractability Assumption

Given a group generatorGGΛ and a positive integer k≤ℓ/3, the subspace assumption is defined as follows [20]. For a given security level Λ, generate the parameters of an instance at random:(2)G,GT,p,e⋅,⋅,g←RGGΛ,B,B∗←RDualℤpℓ,η,β,τ1,τ2,τ3,μ1,μ2,μ3←Rℤp.Calculate the following collection of vectors:(3)Ui=gμ1bi+μ2bk+i+μ3b2k+i,Vi=gτ1ηbi∗+τ2βbk+i∗,Wi=gτ1ηbi∗+τ2βbk+i∗+τ3b2k+i∗,where i=1,2,…,k. Then calculate a vector D such that(4)D=G,GT,p,e⋅,⋅,g,gb1,gb2,…,gb2k,gb3k+1,…,gbℓ,gηb1∗,…,gηbk∗,gβbk+1∗,…,gβb2k∗,gb2k+1∗,…,gbℓ∗,U1,U2,…,Uk,μ3.We assume that, for any probabilistic polynomial time (PPT) algorithmA, the advantage in distinguishing vectors Vi from vectors Wi, where i=1,2,…,k, is negligible in the security parameter Λ or(5)ADVGG,AΛ=PAD,V1,…,Vk=1−PAD,W1,…,Wk=1<1polyΛ.


## 3. Building Blocks

### 3.1. Target Collision Resistant Hash Functions

Given a security parameterΛ, a ℓΛ-bit key k, a group G of prime order pΛ, and a family of keyed hash functions T=Tk:0,1∗⟶ℤpΛ that is indexed by both the key k and the security parameter, the family T is target collision resistant (TCR) if, for any PPT adversary ℋ, her advantage in finding a collision is negligible in the security parameter Λ or in other words (see also [26]):(6)AdvℋTCRΛ=Prk←R0,1ℓΛ;c1←R0,1∗;c2←ℋk,c1:Tkc1=Tkc2∧c1≠c2<1polyΛ.TCR is a weaker requirement of collision resistance than the standard collision resistance of hash functions without keys. Therefore, it is a better match for the hashing used in practice.


### 3.2. Signatures

We recall the definition of digital signatures and their security models.Definition 1.
A signature scheme (SS) is a triplet〈KeyGen, Sign, Verify〉 of PPT algorithms described as follows:(i)
KeyGenΛ: for a required security level Λ, the algorithm returns a pair of keys pk,sk of appropriate length. The key pk is public (for verification), while the key sk is secret (for signing)(ii)
Signsk,m: for an input, the secret key sk, and a message m, the algorithm returns a signature σ of the message m(iii)
Verifypk,m,σ: for an input, the public key pk, the message m, and a string σ, the algorithm outputs 1 if σ is a valid signature of m. Otherwise, it returns 0The adaptive chosen message attack (aCMA) model is stronger than the nonadaptive chosen message attack (naCMA) model. So, we only think about the EUF aCMA game.


### 3.3. Dual-Form Signatures

In 2012, Gerbush et al. [23] proposed the concept of dual-form signatures (DFSs), which is a useful framework for proving the security (existential unforgeability) of signatures from static assumptions. A dual-form signature is defined by the following algorithms [23]:(i)
KeyGenΛ: generates a public key pk and a private key sk for a security parameter Λ(ii)
SignAsk,m: returns a signature σ for a message m and a secret key sk(iii)
SignBsk,m: outputs a signature σ for a message m and a secret key sk(iv)
Verifypk,m,σ: outputs TRUE if the signature σ is valid for the message m and the public key pk. Otherwise, it returns FALSEAs one can see, dual-form signatures apply two variants of the signature algorithm, SignA and SignB. Both algorithms generate valid signatures. This means that they pass the verification algorithm Verify no matter which signature algorithm has been used. However, only one signing algorithm will be used in the real scheme. The other signature algorithm will be used in the security proof/game. To prove the security of dual-form signatures, Gerbush et al. [23] gave a general proof method that works as follows.In a security game, forgeries can be categorised into two (disjoint) types: I and II. They correspond to the signatures obtained by SignA and SignB, respectively. The security proof involves a sequence of transformations of queries obtained from both signature variants SignA and SignB. In the proof, an adversary is asked to produce a valid signature that can be of a specific form. The following list details the required properties:A-I matching: an adversary is only given access to the oracle SignA. It is expected that it is harder for her to produce Type II forgeriesB-II matching: an adversary is only given access to the oracle SignB. It is expected that it is harder for her to produce Type I forgeriesDual-oracle invariance: an adversary is given access to both oracles SignA and SignB. It is expected that the adversary has the same probability of success to generate Type I and Type II forgeriesA dual-form signature is secure if it satisfies the three properties listed above.In [23], the author shows that, by the A-I matching property, it might have a noticeable probability ϵ of producing a Type I forgery but has only a negligible probability of producing any other kind of forgery, and show that ϵ must also be negligible. By the dual-oracle invariance property, the probability of producing a Type I forgery will be close to ϵ if gradually replacing the signing algorithm with SignB, one signature at a time. Once all of the signatures the attacker receives are from SignB, the B-II matching property implies that the probability of producing a Type I forgery must be negligible in the security parameter.If〈Setup, SignA, SignB, Verify〉 is a secure dual-form signature, then 〈Setup, SignA, Verify〉 is existentially unforgeable under an adaptive chosen message attack [23]. This proven technique has a great potential to be a useful tool in the analysis of other cryptographic primitives that use digital signatures.


### 3.4. Threshold Signatures

A threshold signatureΦ consists of the following five algorithms 〈Setup, Share-sign, Share-verify, Combine, and Verify〉.(i)
SetupΛ,t,n takes as input a security parameter Λ∈ℤ, a requested threshold t, and the total number of participants n, where 1≤t≤n. It outputs a set of parameters PP,PK,SK,VK, where PP is the system public parameter, PK is the public key, SK=SK1,…,SKn is the vector of private keys, and VK=VK1,…,VKn is the corresponding verification key vector. The private key SKi is given to the ith participant via a secure channel i=1,2,…,n.(ii)
Share-signPi,SKi,Γ,M is a randomised algorithm executed by Pi. It takes the private key SKi , a message M, and a subset Γ⊂1,…,n of size Γ=t participants who want to sign a message M. It outputs a signature share ui.(iii)
Share-verifyPi,Γ,VKi,ui,M is a deterministic algorithm. It takes as input an identity of Pi∈Γ, its verification key VKi, its signature share ui, and a message M. It outputs valid or invalid depending on whether ui is considered to be a valid share or not.(iv)
CombinePK,M,Γ,Pi,uiPi∈Γ takes as input the public key PK, a message M, and a subset Γ⊂1,…,n of size Γ=t with pairs Pi,ui such that Pi∈Γ and ui is a signature share. This algorithm outputs either a full signature S or ⊥ if the set contains invalid signature shares.(v)
VerifyPK,M,S is a deterministic algorithm that takes as input a message M, the public key PK, and a signature S. This algorithm outputs valid or invalid depending on whether S is a valid signature or not.We assume that an adversaryA can corrupt up to t−1 participants (from all n participants). A can learn all the information stored by the corrupted participants and can listen to all their communication. We consider two types of adversaries: static and adaptive. A static adversary corrupts participants at the beginning of a protocol. An adaptive adversary corrupts participants during protocol execution and chooses the best time so it maximises her chances of compromising the security of noncorrupted participants. As the adaptive adversary captures real-life threats better, we are going to consider threshold signatures that guarantee EUF-aCMA security under adaptive corruption attacks. Consequently, the other case of static corruption attacks is going to be ignored in this work.Given an adaptive adversary and a threshold signatureΦ, to evaluate the security of the signature in this setting, we need to develop an appropriate security notion. Fortunately, we can use the notion formulated by Libert and Yung in their work [LY13].Definition 2.
A threshold signature schemeΦ is existentially unforgeable under adaptively chosen message attacks and adaptive corruption attacks (EUF-aCMA-DCA) if no PPT adversary A has a nonnegligible advantage in the following game between a challenger C and an adversary A.(i)
Initialisation: C runs SetupΛ,t,n.(7)PP,PK,SK,VK←SetupΛ,t,n.The challenger sends public parameters to the adversary. In other words,(8)C⟶A:PP,PK,VK.(ii)
Queries: A can adaptively invoke an arbitrary number of queries. Each query must be either a corruption query or a signing query. The two types are defined below.(i)
Corruption query: If A wants to corrupt the ith participant, then(9)C⟶A:SKi.No more thant−1 private keys can be obtained by A in the whole game.(ii)
Partial signature query: If the adversaryA asks for patrial signature on an arbitrary message M on behalf of a participant Pi∈Γ, then(10)C⟶A:ui.(iii)
Signing query:A asks for a signature on an arbitrary message M and then(11)C⟶A:S.We have thatS is a signature of M.Forgery: A outputs a message M∗ and a signature S∗. She wins if(i)
M∗ was never submitted to the partial signature query or signing query;(ii)
A did not obtain more than t−1 private key shares in the whole game;(iii)
VerifyPK,M∗,S∗ = valid.


## 3.1. Target Collision Resistant Hash Functions

Given a security parameterΛ, a ℓΛ-bit key k, a group G of prime order pΛ, and a family of keyed hash functions T=Tk:0,1∗⟶ℤpΛ that is indexed by both the key k and the security parameter, the family T is target collision resistant (TCR) if, for any PPT adversary ℋ, her advantage in finding a collision is negligible in the security parameter Λ or in other words (see also [26]):(6)AdvℋTCRΛ=Prk←R0,1ℓΛ;c1←R0,1∗;c2←ℋk,c1:Tkc1=Tkc2∧c1≠c2<1polyΛ.TCR is a weaker requirement of collision resistance than the standard collision resistance of hash functions without keys. Therefore, it is a better match for the hashing used in practice.


## 3.2. Signatures

We recall the definition of digital signatures and their security models.Definition 1.
A signature scheme (SS) is a triplet〈KeyGen, Sign, Verify〉 of PPT algorithms described as follows:(i)
KeyGenΛ: for a required security level Λ, the algorithm returns a pair of keys pk,sk of appropriate length. The key pk is public (for verification), while the key sk is secret (for signing)(ii)
Signsk,m: for an input, the secret key sk, and a message m, the algorithm returns a signature σ of the message m(iii)
Verifypk,m,σ: for an input, the public key pk, the message m, and a string σ, the algorithm outputs 1 if σ is a valid signature of m. Otherwise, it returns 0The adaptive chosen message attack (aCMA) model is stronger than the nonadaptive chosen message attack (naCMA) model. So, we only think about the EUF aCMA game.


## 3.3. Dual-Form Signatures

In 2012, Gerbush et al. [23] proposed the concept of dual-form signatures (DFSs), which is a useful framework for proving the security (existential unforgeability) of signatures from static assumptions. A dual-form signature is defined by the following algorithms [23]:(i)
KeyGenΛ: generates a public key pk and a private key sk for a security parameter Λ(ii)
SignAsk,m: returns a signature σ for a message m and a secret key sk(iii)
SignBsk,m: outputs a signature σ for a message m and a secret key sk(iv)
Verifypk,m,σ: outputs TRUE if the signature σ is valid for the message m and the public key pk. Otherwise, it returns FALSEAs one can see, dual-form signatures apply two variants of the signature algorithm, SignA and SignB. Both algorithms generate valid signatures. This means that they pass the verification algorithm Verify no matter which signature algorithm has been used. However, only one signing algorithm will be used in the real scheme. The other signature algorithm will be used in the security proof/game. To prove the security of dual-form signatures, Gerbush et al. [23] gave a general proof method that works as follows.In a security game, forgeries can be categorised into two (disjoint) types: I and II. They correspond to the signatures obtained by SignA and SignB, respectively. The security proof involves a sequence of transformations of queries obtained from both signature variants SignA and SignB. In the proof, an adversary is asked to produce a valid signature that can be of a specific form. The following list details the required properties:A-I matching: an adversary is only given access to the oracle SignA. It is expected that it is harder for her to produce Type II forgeriesB-II matching: an adversary is only given access to the oracle SignB. It is expected that it is harder for her to produce Type I forgeriesDual-oracle invariance: an adversary is given access to both oracles SignA and SignB. It is expected that the adversary has the same probability of success to generate Type I and Type II forgeriesA dual-form signature is secure if it satisfies the three properties listed above.In [23], the author shows that, by the A-I matching property, it might have a noticeable probability ϵ of producing a Type I forgery but has only a negligible probability of producing any other kind of forgery, and show that ϵ must also be negligible. By the dual-oracle invariance property, the probability of producing a Type I forgery will be close to ϵ if gradually replacing the signing algorithm with SignB, one signature at a time. Once all of the signatures the attacker receives are from SignB, the B-II matching property implies that the probability of producing a Type I forgery must be negligible in the security parameter.If〈Setup, SignA, SignB, Verify〉 is a secure dual-form signature, then 〈Setup, SignA, Verify〉 is existentially unforgeable under an adaptive chosen message attack [23]. This proven technique has a great potential to be a useful tool in the analysis of other cryptographic primitives that use digital signatures.


## 3.4. Threshold Signatures

A threshold signatureΦ consists of the following five algorithms 〈Setup, Share-sign, Share-verify, Combine, and Verify〉.(i)
SetupΛ,t,n takes as input a security parameter Λ∈ℤ, a requested threshold t, and the total number of participants n, where 1≤t≤n. It outputs a set of parameters PP,PK,SK,VK, where PP is the system public parameter, PK is the public key, SK=SK1,…,SKn is the vector of private keys, and VK=VK1,…,VKn is the corresponding verification key vector. The private key SKi is given to the ith participant via a secure channel i=1,2,…,n.(ii)
Share-signPi,SKi,Γ,M is a randomised algorithm executed by Pi. It takes the private key SKi , a message M, and a subset Γ⊂1,…,n of size Γ=t participants who want to sign a message M. It outputs a signature share ui.(iii)
Share-verifyPi,Γ,VKi,ui,M is a deterministic algorithm. It takes as input an identity of Pi∈Γ, its verification key VKi, its signature share ui, and a message M. It outputs valid or invalid depending on whether ui is considered to be a valid share or not.(iv)
CombinePK,M,Γ,Pi,uiPi∈Γ takes as input the public key PK, a message M, and a subset Γ⊂1,…,n of size Γ=t with pairs Pi,ui such that Pi∈Γ and ui is a signature share. This algorithm outputs either a full signature S or ⊥ if the set contains invalid signature shares.(v)
VerifyPK,M,S is a deterministic algorithm that takes as input a message M, the public key PK, and a signature S. This algorithm outputs valid or invalid depending on whether S is a valid signature or not.We assume that an adversaryA can corrupt up to t−1 participants (from all n participants). A can learn all the information stored by the corrupted participants and can listen to all their communication. We consider two types of adversaries: static and adaptive. A static adversary corrupts participants at the beginning of a protocol. An adaptive adversary corrupts participants during protocol execution and chooses the best time so it maximises her chances of compromising the security of noncorrupted participants. As the adaptive adversary captures real-life threats better, we are going to consider threshold signatures that guarantee EUF-aCMA security under adaptive corruption attacks. Consequently, the other case of static corruption attacks is going to be ignored in this work.Given an adaptive adversary and a threshold signatureΦ, to evaluate the security of the signature in this setting, we need to develop an appropriate security notion. Fortunately, we can use the notion formulated by Libert and Yung in their work [LY13].Definition 2.
A threshold signature schemeΦ is existentially unforgeable under adaptively chosen message attacks and adaptive corruption attacks (EUF-aCMA-DCA) if no PPT adversary A has a nonnegligible advantage in the following game between a challenger C and an adversary A.(i)
Initialisation: C runs SetupΛ,t,n.(7)PP,PK,SK,VK←SetupΛ,t,n.The challenger sends public parameters to the adversary. In other words,(8)C⟶A:PP,PK,VK.(ii)
Queries: A can adaptively invoke an arbitrary number of queries. Each query must be either a corruption query or a signing query. The two types are defined below.(i)
Corruption query: If A wants to corrupt the ith participant, then(9)C⟶A:SKi.No more thant−1 private keys can be obtained by A in the whole game.(ii)
Partial signature query: If the adversaryA asks for patrial signature on an arbitrary message M on behalf of a participant Pi∈Γ, then(10)C⟶A:ui.(iii)
Signing query:A asks for a signature on an arbitrary message M and then(11)C⟶A:S.We have thatS is a signature of M.Forgery: A outputs a message M∗ and a signature S∗. She wins if(i)
M∗ was never submitted to the partial signature query or signing query;(ii)
A did not obtain more than t−1 private key shares in the whole game;(iii)
VerifyPK,M∗,S∗ = valid.


## 4. Construction

In this section, we present a threshold signatureΦ based on dual pairing vector spaces. The security of the proposed scheme is proven under the subspace assumption. The algorithms of the signature are as follows.SetupΛ,t,n: Given the parameters Λ, t, and n, the following steps are executed:(i)
Compute group parameters by running the algorithmGGΛ:(12)G,GT,p,e⋅,⋅,g←GGΛ.Select a hash functionH, where H:0,1∗⟶ℤp is a target collision-resistant hash function.(ii)
Setℓ=6 and sample a pair of random dual orthonormal bases.(13)D,D∗←RDualℤpℓ.Letd1,…,d6 denote the elements of D and let d1∗,…,d6∗ denote the elements of D∗, where di,di∗∈ℤpℓ and di,di∗=ψ, for i=1,…,6.(iii)
Choose random valuesα,θ,σ∈ℤp∗ and a random polynomial Fx=∑j=0t−1ajxj of degree t−1 (where t is the threshold value and aj∈ℤp for j=0,…,t−1, and a0=α) and compute the partial decryption keys(14)SKi1=gFiθd1∗,SKi2=gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗,and verification key(15)VKi=eℓgd1,SKi1=eg,gFiθψ,fori=1,…,n, where ri1,ri2←Rℤp.(iv)
Publish the public parametersPP=G,GT,p,e⋅,⋅,g,H⋅, public key PK=Z=eg,gαθψ,gd1,gd2,gd3,gd4, and verification key VK=VK1,…,VKn on the bulletin board. Partial private key SKi=SKi1,SKi2 is privately given to Pi, for i=1,…,n.Share-SignPi,SKi,Γ,M: Denote the currently active set of t participants by Γ. Pi selects at random ki∈ℤp and computes its partial signature (or signature share) si=ui,Ki using SKi according to(16)ui=SKi1λi+HMkiSKi2ki,Ki=VKiki,whereλi=∏j∈Γ,j≠i−j/i−j, and then sends si=ui,Ki to the combiner.Share-VerifyPi,Γ,VKi,ui,M: Given Pi’s Pi∈Γ verification key VKi and the partial signature si=ui,Ki of the message M, the combiner verifies si by checking if(17)eℓgd1gd2gd3gd4,ui=?VKiλiKiHM.If the above equality holds,si=ui,Ki is valid. Otherwise, the combiner declares that Pi is corrupted.CombinePK,M,Γ,Pi,siPi∈Γ:Given the setΓ, the public key PK, the message M, and t valid shares Pi,siPi∈Γ, the combiner computes the signature S=S1,S2 as(18)S1=∏i∈Γui,S2=∏i∈ΓKi.VerifyPK,M,S : For a signature S=S1,S2 of a message M with respect to a public key PK, the algorithm outputs valid (or 1) if the following equation holds:(19)eℓgd1gd2gd3gd4,S1=?ZS2HM.Otherwise, it returns invalid (or0).


### 4.1. Correctness

We are going to show that the two verification algorithms Share-Verify and Verify always accept the well-formed shares and the final signatures. The Share-Verify algorithm accepts the input if equation (17) holds. We start from the left-hand side of the equation and run through a sequence of transformations, so we arrive at the right-hand side of equation (17).(20)eℓgd1gd2gd3gd4,ui=eℓgd1gd2gd3gd4,SKi1λi+HMkiSKi2ki=eℓgd1gd2gd3gd4,SKi1λi+HMkieℓgd1gd2gd3gd4,SKi2ki=eℓgd1gd2gd3gd4,gFiθd1∗λi+HMkieℓgd1gd2gd3gd4,SKi2ki=eg,gFiθψλi+HMkieℓgd1gd2gd3gd4,SKi2ki=VKiλiKiHMeℓgd1gd2gd3gd4,SKi2ki=VKiλiKiHMeℓgd1gd2gd3gd4,gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗⋅ki=VKiλiKHMeg,gri1θd1d1∗−ri1θd2d2∗+ri2σd3d3∗−ri2σd4d4∗⋅ki=VKiλiKiHMeg,gri1θψ−ri1θψ+ri2σψ−ri2σψ⋅ki=VKiλiKiHM.The Verify algorithm uses equation (19) to check if the signatures are valid. In a similar vein, we start from the left-hand side of equation (19) and show how to arrive at the right-hand side of the equation.(21)S1=∏i∈Γui=∏i∈ΓSKi1λi+HMkiSKi2ki=∏i∈ΓSKi1λi+HMki⋅∏i∈ΓSKi2ki=∏i∈ΓSKi1λiSKi1HMki⋅∏i∈ΓSKi2ki=∏i∈ΓgFiθd1∗λi∏i∈ΓSKi1HMki∏i∈ΓSKi2ki=g∑i∈ΓFiλiθd1∗∏i∈ΓSKi1HMki∏i∈ΓSKi2ki=gαθd1∗∏i∈ΓSKi1HMki∏i∈Γgri1ki⋅θd1∗−ri1ki⋅θd2∗+ri2ki⋅σd3∗−ri2ki⋅σd4∗=gαθd1∗gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗∏i∈ΓSKi1HMki,where R1=∑i∈Γri1ki, R2=∑i∈Γri2ki, and let W=eℓgd1gd2gd3gd4,S1, so we have that(22)W=eℓgd1gd2gd3gd4,gαθd1∗gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗∏i∈ΓSKi1HMki=eg,gαθψeℓgd1gd2gd3gd4,gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗∏i∈Γeg,gθψHMFikiZ⋅eℓg,gR1θd1∗d1−R1θd2∗d2+R2σd3∗d3−R2σd4∗d4∏i∈ΓKiHMZ⋅eg,gR1θψ−R1θψ+R2σψ−R2σψS2HMZ⋅S2HM.


## 4.1. Correctness

We are going to show that the two verification algorithms Share-Verify and Verify always accept the well-formed shares and the final signatures. The Share-Verify algorithm accepts the input if equation (17) holds. We start from the left-hand side of the equation and run through a sequence of transformations, so we arrive at the right-hand side of equation (17).(20)eℓgd1gd2gd3gd4,ui=eℓgd1gd2gd3gd4,SKi1λi+HMkiSKi2ki=eℓgd1gd2gd3gd4,SKi1λi+HMkieℓgd1gd2gd3gd4,SKi2ki=eℓgd1gd2gd3gd4,gFiθd1∗λi+HMkieℓgd1gd2gd3gd4,SKi2ki=eg,gFiθψλi+HMkieℓgd1gd2gd3gd4,SKi2ki=VKiλiKiHMeℓgd1gd2gd3gd4,SKi2ki=VKiλiKiHMeℓgd1gd2gd3gd4,gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗⋅ki=VKiλiKHMeg,gri1θd1d1∗−ri1θd2d2∗+ri2σd3d3∗−ri2σd4d4∗⋅ki=VKiλiKiHMeg,gri1θψ−ri1θψ+ri2σψ−ri2σψ⋅ki=VKiλiKiHM.The Verify algorithm uses equation (19) to check if the signatures are valid. In a similar vein, we start from the left-hand side of equation (19) and show how to arrive at the right-hand side of the equation.(21)S1=∏i∈Γui=∏i∈ΓSKi1λi+HMkiSKi2ki=∏i∈ΓSKi1λi+HMki⋅∏i∈ΓSKi2ki=∏i∈ΓSKi1λiSKi1HMki⋅∏i∈ΓSKi2ki=∏i∈ΓgFiθd1∗λi∏i∈ΓSKi1HMki∏i∈ΓSKi2ki=g∑i∈ΓFiλiθd1∗∏i∈ΓSKi1HMki∏i∈ΓSKi2ki=gαθd1∗∏i∈ΓSKi1HMki∏i∈Γgri1ki⋅θd1∗−ri1ki⋅θd2∗+ri2ki⋅σd3∗−ri2ki⋅σd4∗=gαθd1∗gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗∏i∈ΓSKi1HMki,where R1=∑i∈Γri1ki, R2=∑i∈Γri2ki, and let W=eℓgd1gd2gd3gd4,S1, so we have that(22)W=eℓgd1gd2gd3gd4,gαθd1∗gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗∏i∈ΓSKi1HMki=eg,gαθψeℓgd1gd2gd3gd4,gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗∏i∈Γeg,gθψHMFikiZ⋅eℓg,gR1θd1∗d1−R1θd2∗d2+R2σd3∗d3−R2σd4∗d4∏i∈ΓKiHMZ⋅eg,gR1θψ−R1θψ+R2σψ−R2σψS2HMZ⋅S2HM.


## 5. Security

Theorem 1.
Given our threshold signatureΦ = 〈Setup, Share-sign, Share-Verify, Combine, and Verify〉, assume that the subspace intractability assumption holds; then the signature scheme Φ is EUF-aCMA-DCA secure (or can withstand existential forgeries under adaptive chosen message and adaptive corruption attacks).We prove the theorem using the hybrid argument for a sequence of games similar to [23]. Like [23], our proof makes use of normal signatures and semifunctional semisignatures.Type I signatures are normal signatures ofS1:(23)S1=gα+R3HMθd1∗gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗,whereR1,R2∈ℤp,R3=∑i∈ΓFiki.Type II signatures are semisignatures ofS1:(24)S1=gα+R3HMθd1∗gR1θd1∗−R1θd2∗+R2σd3∗−R2σd4∗+z5d5∗+z6d6∗,where R1,R2,z5,z6∈ℤp,R3=∏i∈ΓFikiθ.We apply the dual-form signature technique to prove the security of our threshold signatures. We start from a real security game, denoted byGame0 followed by the sequence Game1, …, Gameq and Gamefinal.(i)
Game0 is identical to the EUF-aCMA-DCA game, an adversary produces a Type I signature as a forgery, and the advantage of adversary A is defined accordingly. Game0 is played between a challenger C and an adversary A as follows.Initialisation:C runs SetupΛ,t,n to get (PP, PK, SK, VK), where(25)PP=G,GT,p,e⋅,⋅,g,PK=Z=eg,gαθψ,gd1,gd2,gd3,gd4,H⋅,SK=SK1,…,SKnwithSKi=SKi1,SKi2,VK=VK1,…,VKn.Queries:A adaptively makes a number q of queries.Each query can be either a corruption one or a signing one.A cannot make more than t−1 corruption queries.A gets also valid signatures for messages of her choice.Forgery:A outputs S∗=S1∗,S2 for a message M∗ that has not been queried.C wins the game if VerifyPK,M∗,S∗=1.(ii)
GameJ1≤J≤q is like GameJ−1, except that the challenger C answers the first J signing query by returning Type II signatures, and the last q−J signing queries are answered using Type I signatures. The process is as follows.Initialisation:C runs SetupΛ,t,n to get PP,PK,SK,VK, where(26)PP=G,GT,p,e⋅,⋅,g,PK=Z=eg,gαθψ,gd1,gd2,gd3,gd4,H⋅,SK=SK1,…,SKnwithSKi=SKi1,SKi2,VK=VK1,…,VKn.Queries:A adaptively makes a number q of queries.Each query can be either a corruption one or a signing one.A cannot make more than t−1 corruption queries.A gets Type II signatures of the first J signing queries and gets Type I signatures of the last q−J signing queries for messages of her choice.Forgery:A outputs S∗=S1∗,S2 for a message M∗ that has not been queried.A wins the game if VerifyPK,M∗,S∗=1 and the probability is the same for the Type I and Type II forgeries.(iii)
Gamefinal is identical to Gameq, except that the challenger C answers the corruption query by returning the private key shares which contain random d5∗,d6∗ , signing the query by returning Type II signatures, and needs to output a forgery of the same type. The process is as follows.Initialisation:C runs SetupΛ,t,n to get (PP, PK, SK, VK), where(27)PP=G,GT,p,e⋅,⋅,g,PK=Z=eg,gαθψ,gd1,gd2,gd3,gd4,H⋅,SK=SK1,…,SKnwithSKi=SKi1,SKi2,VK=VK1,…,VKn.Queries:A adaptively makes a number q of queries.Each query can be either a corruption one or a signing one.She cannot make more thant−1 corruption queries.A gets the secret key SKi=SKi1,SKi2gτ1d5∗+τ2d6∗ (where τ1,τ2∈ℤp) when she corrupts the participant i.A gets Type II signatures of signing queries for messages of her choice.Forgery:A outputs S∗=S1∗,S2 for a message M∗ that has not been queried.A wins the game if VerifyPK,M∗,S∗=1 and the forgery signature is Type I.We will prove that Theorem1 is true through a sequence of claims.


### 5.1. Claim 1

InGame0, adversary A has a negligible chance of outputting a Type II signature if the subspace assumption with k=2 and ℓ=6 holds.Proof.
We construct an algorithmD that, on the input of an instance G,GT,p,e⋅,⋅,g,gb1,…,gb4,gηb1∗,gηb2∗,gβb3∗,gβb4∗,gb5∗,gb6∗,U1=gμ1b1+μ2b3+μ3b5,U2=gμ1b2+μ2b4+μ3b6,μ3,T1,T2, decides T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗ or T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗.
Initialisation: To compute the system public parameters and the participant’s private key, D first selects a random invertible matrix A=a11a12a21a22∈ℤp2×2 and a TCR hash function H:0,1∗⟶ℤp . The public parameter PP is G,GT,p,e⋅,⋅,g,H.
D defines the dual orthonormal bases F=f1,f2,f3,f4,f5,f6 and F∗=f1∗,f2∗,f3∗,f4∗,f5∗,f6∗ by(28)f1=ηb1∗,f2=ηb2∗,f3=βb3∗,f4=βb4∗,f5=b5∗,f6=b6∗,f1∗=η−1b1,f2∗=η−1b2,f3∗=β−1b3,f4∗=β−1b4,f5∗=b5,f6∗=b6.
D sets D=F×A,D∗=F∗×A∗, where A=I4×400A and A∗=I4×400A′−1 (A′ denotes the transpose of A). So, we have that di=fi,di∗=fi∗, for i=1,…,4, and d5,d6=f5,f6A=a11f5+a11f6,a21f5+a22f6, d5∗,d6∗=f5∗,f6∗A′−1. By Lemma 1 in [20], D and D∗ are a pair of properly distributed dual orthonormal bases and reveal no information about A.
D picks random values α,θ′,σ′∈ℤp and a random polynomial Fx∈ℤp with degree t−1 and implicitly sets θ=θ′η,σ=σ′β, and F0=α. D computes the public key as follows:(29)Z=eℓgb1,gηb1∗αθ′=eg,gαθ′b1⋅ηb1∗=eg,gαθ′ηη−1b1⋅ηb1∗=eg,gα⋅θ′η⋅f1∗⋅f1=eg,gαθd1∗⋅d1,gd1=gηb1∗,gd2=gηb2∗,gd3=gβb3∗,gd4=gβb4∗.
Sincegb5∗a11gb6∗a21=ga11b5∗+a21b6∗=ga11f5+a21f6=gd5, we have that gd5=ga11b5∗+a21b6∗, and we also can get that gd6=ga12b5∗+a22b6∗ by using the same method. D selects ri1,ri2←Rℤp (for i=1,…,n) and computes Pi’s partial decryption key:(30)SKi1=gb1Fiθ′=gFi⋅ηθ′⋅η−1b1=gFiθd1∗,SKi2=gb1ri1θ′gb2−ri1θ′gb3ri2σ′gb4−ri2σ′=gri1θ′ηf1∗−ri1θ′ηf2∗+ri2σ′βf3∗−ri2σ′βf4∗=gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗.
Finally,D sends G,GT,p,e⋅,⋅,g,H⋅, and PK=Z,gd1,gd2,gd3,gd4 to adversary A.
Query. Since D knows all SKi, it can perfectly answer corruption queries and signing queries.
A produces a forgery signature M∗,S∗, where S∗=S1∗,S2. Firstly D must check that Verify PK,M∗,S∗ = 1; if not, then D will abort. In addition, D must verify that it has not received a Type I forgery signature. Notice that D needs the output of A to be a Type II forgery signature in order to defeat the subspace assumption with k=2 and l=6. To do this, D can check whether eℓgd5gd6,S1∗=1GT or not. If so, the forgery signature M∗,S∗ is a Type I signature, and then D will abort. Otherwise, D uses the forgery signature to determine what subspace T1,T2 is in. Since D knows the value θ′,α, it can simply check whether eℓT1T2,S1∗/eℓgα+R3HM∗b1θ′,T1=1GT or not. If so, T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗. Otherwise, T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗.


### 5.2. Claim 2

The adversary outputs a Type I forgery with negligibly different probabilities inGameJ and GameJ+1 if the subspace assumption with k=2 and l=6 holds.Proof.
D begins by taking an instance G,GT,p,e⋅,⋅,g,gb1,…,gb4,gηb1∗,gηb2∗,gβb3∗,gβb4∗,gb5∗,gb6∗,U1=gμ1b1+μ2b3+μ3b5,U2=gμ1b2+μ2b4+μ3b6,μ3,T1,T2. D’s task is to decide T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗ or T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗, T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗. Recall that A must obtain Type II signatures from the first J signing queries and Type I signatures at the last q−J−1 queries. The Jth query will be a Type I signature or Type II signature depending on which subspace of T1,T2 is in.
Initialisation: To compute the public key, participants’ partial decryption key, and the verification key,D first picks a random invertible matrix A∈ℤp2×2 and a TCR hash function H:0,1∗⟶ℤp. The public parameter PP is G,GT,p,e⋅,⋅,g,H; D defines the dual orthonormal bases B=b1,b2,b3,b4,b5,b6 and B∗=b1∗,b2∗,b3∗,b4∗,b5∗,b6∗. D implicitly sets D=B×I4×400A, D∗=B∗×I4×400A′−1, θ=η, and σ=β. So D can generate gd1=gb1, gd2=gb2, gd3=gb3, and gd4=gb4 and also can generate gθd1∗=gηb1∗, gθd2∗=gηb2∗, gσd3∗=gβb3∗, and gσd4∗=gβb4∗. D picks a random value α,r∈ℤp and a random polynomial Fx∈ℤp with degree t−1 and sets F0=α. D computes(31)Z=eℓgb1,gηb1∗α=eg,gαθd1⋅d1∗,as well as Pi’s partial decryption key(32)SKi1=gηb1∗Fi=gθd1∗Fi,SKi2=grηb1∗g−rηb2∗grβb3∗g−rβb4∗=grθd1∗−rθd2∗+rσd3∗−rσd4∗,for i=1,…,n. Finally, D sends PP,PK=Z,gd1,gd2,gd3,gd4 to adversary A.
Query:D can perfectly answer private key queries (since it knows SKi) and answer A′s signing queries depending on the value of j∈1,…,q.Casej<J: to generate a signature share on a message Mj on behalf of Pii∈1,…,n, D chooses ki,τ5,τ6∈Rℤp and computes a Type II signature share ui=SKi1λi+HMkiSKi2kigτ5b5∗gτ6b6∗.Casej>J: in this case, D chooses ki∈Rℤp and computes a Type I signature share ui=SKi1λi+HMkiSKi2ki.Casej=J: in this case, D generates a signature share ui=SKi1λi+HMkiT1kiT2−ki. It is easy to see that, in the situation S1=∏i∈Γui will be a Type II signature when T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗, or a Type I signature when T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗.
A sends a forgery signature M∗,S∗ to D. Firstly, D must check that Verify PK,M∗,S∗ = 1; if not, then D will abort. In addition, D must identify which type of forgery signature it is. To do this, D will check whether eℓU1U2,S1∗/eℓgα+R3HM∗θd1∗,U1=1GT or not. If so, the forgery signature M∗,S∗ is a Type I signature. Otherwise, it is a Type II signature. At this stage, D returns 0 (meaning that it believes that T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗) if S∗ is a Type I signature. If S∗ is a Type II signature, D returns 1 and bets that T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗.


### 5.3. Claim 3

InGamefinal, adversary A cannot output a Type I forgery signature as long as the subspace assumption holds with k=1 and l=6.Proof.
D begins by taking an instance G,GT,p,e⋅,⋅,g,gb1,gb2,gb4,gb5,gb6,gηb1∗,gβb2∗,gb3∗,gb4∗,gb5∗,gb6∗,U1=gμ1b1+μ2b2+μ3b3,μ3,T1. D’s task is to decide T1=gτ1ηb1∗+τ2βb2∗ or T1=gτ1ηb1∗+τ2βb2∗+τ3b3∗.
Initialisation:D picks a TCR hash function H:0,1∗⟶ℤp. The public parameter PP is G,GT,p,e⋅,⋅,g,H. D implicitly defines the dual orthonormal bases D=d1,…,d6 and D∗=d1∗,…,d6∗ as(33)d1=b4∗,d2=b3∗,d3=b5∗,d4=b6∗,d5=b1∗,d6=b2∗,d1∗=b4,d2∗=b3,d3∗=b5,d4∗=b6,d5∗=b1,d6∗=b2.
We note thatD,D∗ are properly distributed dual orthonormal bases, and D can generate gd1,gd2,gd3,gd4 and gd1∗,gd3∗,gd4∗,gd5∗,gd6∗ but cannot generate gd2∗. D picks random values θ,σ,α∈ℤp and a random polynomial Fx∈ℤp with degree t−1 and sets F0=α. D computes(34)Z=eℓgb4,gb4∗αθ=eg,gαθd1⋅d1∗.
D picks random values ri1′,ri2,t5,t6∈ℤp and sets ri1=μ3ri1′. D computes Pi’s partial decryption key:(35)SKi1=gb4Fiθ=gFiθd1∗,SKi2=gb4μ3ri1′θgb5ri2σgb1t5gb2∗t6U1−θri1′gb6−ri2σ=gd1∗μ3ri1′θgd3∗ri2σgd5∗t5gd6∗t6U1−θri1′gb6−ri2σ=gμ3ri1′θd1∗+ri2σd3∗+t5d5∗+t6d6∗U1−θri1′gb6−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗U1−θri1′gb6−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗gμ1b1+μ2b2+μ3b3−θri1′gd4∗−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗gμ1d5∗+μ2d6∗+μ3d2∗−θri1′gd4∗−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗g−θμ3ri1′d2∗−μ1θri1′d5∗−μ2θri1′d6∗g−ri2σd4∗=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗g−ri1θd2∗−ri2σd4∗−μ1θri1′d5∗−μ2θri1′d6∗=gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗+t5′d5∗+t6′d6∗,where t5′=t5−μ1θri1′ and t6′=t6−μ2θri1′, for i=1,…,n.
Finally,D sends PP,PK=Z,gd1,gd2,gd3,gd4 to adversary A.
Query. SinceD knows all SKi, it can perfectly answer corruption queries and signing queries.
A produces a forgery signature M∗,S∗. Firstly, D must check that Verify PK,M∗,S∗ = “true”; if not, then D will abort. In addition, D must verify that it has not received a Type II forgery signature. To do this, D can check whether eℓgd5gd6,S1∗=1GT or not. If not, the forgery signature M∗,S∗ is a Type II signature; then D will abort. Notice that D needs the output of A to be a Type I forgery signature in order to defeat the subspace assumption with k=1 and l=6. Finally, D uses the forgery signature to determine what subspace T1 is in. D can simply check whether eℓS1∗,T1=1GT or not. If so, T1=gτ1ηb1∗+τ2βb2∗. Otherwise, T1=gτ1ηb1∗+τ2βb2∗+τ3b3∗.
It comes thatA ’s advantage is thus negligible if the subspace assumption with k=1 and l=6 holds.
According to Claims 1, 2, and 3, the signature schemeΦ is EUF-aCMA-DCA secure.


## 5.1. Claim 1

InGame0, adversary A has a negligible chance of outputting a Type II signature if the subspace assumption with k=2 and ℓ=6 holds.Proof.
We construct an algorithmD that, on the input of an instance G,GT,p,e⋅,⋅,g,gb1,…,gb4,gηb1∗,gηb2∗,gβb3∗,gβb4∗,gb5∗,gb6∗,U1=gμ1b1+μ2b3+μ3b5,U2=gμ1b2+μ2b4+μ3b6,μ3,T1,T2, decides T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗ or T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗.
Initialisation: To compute the system public parameters and the participant’s private key, D first selects a random invertible matrix A=a11a12a21a22∈ℤp2×2 and a TCR hash function H:0,1∗⟶ℤp . The public parameter PP is G,GT,p,e⋅,⋅,g,H.
D defines the dual orthonormal bases F=f1,f2,f3,f4,f5,f6 and F∗=f1∗,f2∗,f3∗,f4∗,f5∗,f6∗ by(28)f1=ηb1∗,f2=ηb2∗,f3=βb3∗,f4=βb4∗,f5=b5∗,f6=b6∗,f1∗=η−1b1,f2∗=η−1b2,f3∗=β−1b3,f4∗=β−1b4,f5∗=b5,f6∗=b6.
D sets D=F×A,D∗=F∗×A∗, where A=I4×400A and A∗=I4×400A′−1 (A′ denotes the transpose of A). So, we have that di=fi,di∗=fi∗, for i=1,…,4, and d5,d6=f5,f6A=a11f5+a11f6,a21f5+a22f6, d5∗,d6∗=f5∗,f6∗A′−1. By Lemma 1 in [20], D and D∗ are a pair of properly distributed dual orthonormal bases and reveal no information about A.
D picks random values α,θ′,σ′∈ℤp and a random polynomial Fx∈ℤp with degree t−1 and implicitly sets θ=θ′η,σ=σ′β, and F0=α. D computes the public key as follows:(29)Z=eℓgb1,gηb1∗αθ′=eg,gαθ′b1⋅ηb1∗=eg,gαθ′ηη−1b1⋅ηb1∗=eg,gα⋅θ′η⋅f1∗⋅f1=eg,gαθd1∗⋅d1,gd1=gηb1∗,gd2=gηb2∗,gd3=gβb3∗,gd4=gβb4∗.
Sincegb5∗a11gb6∗a21=ga11b5∗+a21b6∗=ga11f5+a21f6=gd5, we have that gd5=ga11b5∗+a21b6∗, and we also can get that gd6=ga12b5∗+a22b6∗ by using the same method. D selects ri1,ri2←Rℤp (for i=1,…,n) and computes Pi’s partial decryption key:(30)SKi1=gb1Fiθ′=gFi⋅ηθ′⋅η−1b1=gFiθd1∗,SKi2=gb1ri1θ′gb2−ri1θ′gb3ri2σ′gb4−ri2σ′=gri1θ′ηf1∗−ri1θ′ηf2∗+ri2σ′βf3∗−ri2σ′βf4∗=gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗.
Finally,D sends G,GT,p,e⋅,⋅,g,H⋅, and PK=Z,gd1,gd2,gd3,gd4 to adversary A.
Query. Since D knows all SKi, it can perfectly answer corruption queries and signing queries.
A produces a forgery signature M∗,S∗, where S∗=S1∗,S2. Firstly D must check that Verify PK,M∗,S∗ = 1; if not, then D will abort. In addition, D must verify that it has not received a Type I forgery signature. Notice that D needs the output of A to be a Type II forgery signature in order to defeat the subspace assumption with k=2 and l=6. To do this, D can check whether eℓgd5gd6,S1∗=1GT or not. If so, the forgery signature M∗,S∗ is a Type I signature, and then D will abort. Otherwise, D uses the forgery signature to determine what subspace T1,T2 is in. Since D knows the value θ′,α, it can simply check whether eℓT1T2,S1∗/eℓgα+R3HM∗b1θ′,T1=1GT or not. If so, T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗. Otherwise, T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗.


## 5.2. Claim 2

The adversary outputs a Type I forgery with negligibly different probabilities inGameJ and GameJ+1 if the subspace assumption with k=2 and l=6 holds.Proof.
D begins by taking an instance G,GT,p,e⋅,⋅,g,gb1,…,gb4,gηb1∗,gηb2∗,gβb3∗,gβb4∗,gb5∗,gb6∗,U1=gμ1b1+μ2b3+μ3b5,U2=gμ1b2+μ2b4+μ3b6,μ3,T1,T2. D’s task is to decide T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗ or T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗, T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗. Recall that A must obtain Type II signatures from the first J signing queries and Type I signatures at the last q−J−1 queries. The Jth query will be a Type I signature or Type II signature depending on which subspace of T1,T2 is in.
Initialisation: To compute the public key, participants’ partial decryption key, and the verification key,D first picks a random invertible matrix A∈ℤp2×2 and a TCR hash function H:0,1∗⟶ℤp. The public parameter PP is G,GT,p,e⋅,⋅,g,H; D defines the dual orthonormal bases B=b1,b2,b3,b4,b5,b6 and B∗=b1∗,b2∗,b3∗,b4∗,b5∗,b6∗. D implicitly sets D=B×I4×400A, D∗=B∗×I4×400A′−1, θ=η, and σ=β. So D can generate gd1=gb1, gd2=gb2, gd3=gb3, and gd4=gb4 and also can generate gθd1∗=gηb1∗, gθd2∗=gηb2∗, gσd3∗=gβb3∗, and gσd4∗=gβb4∗. D picks a random value α,r∈ℤp and a random polynomial Fx∈ℤp with degree t−1 and sets F0=α. D computes(31)Z=eℓgb1,gηb1∗α=eg,gαθd1⋅d1∗,as well as Pi’s partial decryption key(32)SKi1=gηb1∗Fi=gθd1∗Fi,SKi2=grηb1∗g−rηb2∗grβb3∗g−rβb4∗=grθd1∗−rθd2∗+rσd3∗−rσd4∗,for i=1,…,n. Finally, D sends PP,PK=Z,gd1,gd2,gd3,gd4 to adversary A.
Query:D can perfectly answer private key queries (since it knows SKi) and answer A′s signing queries depending on the value of j∈1,…,q.Casej<J: to generate a signature share on a message Mj on behalf of Pii∈1,…,n, D chooses ki,τ5,τ6∈Rℤp and computes a Type II signature share ui=SKi1λi+HMkiSKi2kigτ5b5∗gτ6b6∗.Casej>J: in this case, D chooses ki∈Rℤp and computes a Type I signature share ui=SKi1λi+HMkiSKi2ki.Casej=J: in this case, D generates a signature share ui=SKi1λi+HMkiT1kiT2−ki. It is easy to see that, in the situation S1=∏i∈Γui will be a Type II signature when T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗, or a Type I signature when T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗.
A sends a forgery signature M∗,S∗ to D. Firstly, D must check that Verify PK,M∗,S∗ = 1; if not, then D will abort. In addition, D must identify which type of forgery signature it is. To do this, D will check whether eℓU1U2,S1∗/eℓgα+R3HM∗θd1∗,U1=1GT or not. If so, the forgery signature M∗,S∗ is a Type I signature. Otherwise, it is a Type II signature. At this stage, D returns 0 (meaning that it believes that T1=gτ1ηb1∗+τ2βb3∗,T2=gτ1ηb2∗+τ2βb4∗) if S∗ is a Type I signature. If S∗ is a Type II signature, D returns 1 and bets that T1=gτ1ηb1∗+τ2βb3∗+τ3b5∗,T2=gτ1ηb2∗+τ2βb4∗+τ3b6∗.


## 5.3. Claim 3

InGamefinal, adversary A cannot output a Type I forgery signature as long as the subspace assumption holds with k=1 and l=6.Proof.
D begins by taking an instance G,GT,p,e⋅,⋅,g,gb1,gb2,gb4,gb5,gb6,gηb1∗,gβb2∗,gb3∗,gb4∗,gb5∗,gb6∗,U1=gμ1b1+μ2b2+μ3b3,μ3,T1. D’s task is to decide T1=gτ1ηb1∗+τ2βb2∗ or T1=gτ1ηb1∗+τ2βb2∗+τ3b3∗.
Initialisation:D picks a TCR hash function H:0,1∗⟶ℤp. The public parameter PP is G,GT,p,e⋅,⋅,g,H. D implicitly defines the dual orthonormal bases D=d1,…,d6 and D∗=d1∗,…,d6∗ as(33)d1=b4∗,d2=b3∗,d3=b5∗,d4=b6∗,d5=b1∗,d6=b2∗,d1∗=b4,d2∗=b3,d3∗=b5,d4∗=b6,d5∗=b1,d6∗=b2.
We note thatD,D∗ are properly distributed dual orthonormal bases, and D can generate gd1,gd2,gd3,gd4 and gd1∗,gd3∗,gd4∗,gd5∗,gd6∗ but cannot generate gd2∗. D picks random values θ,σ,α∈ℤp and a random polynomial Fx∈ℤp with degree t−1 and sets F0=α. D computes(34)Z=eℓgb4,gb4∗αθ=eg,gαθd1⋅d1∗.
D picks random values ri1′,ri2,t5,t6∈ℤp and sets ri1=μ3ri1′. D computes Pi’s partial decryption key:(35)SKi1=gb4Fiθ=gFiθd1∗,SKi2=gb4μ3ri1′θgb5ri2σgb1t5gb2∗t6U1−θri1′gb6−ri2σ=gd1∗μ3ri1′θgd3∗ri2σgd5∗t5gd6∗t6U1−θri1′gb6−ri2σ=gμ3ri1′θd1∗+ri2σd3∗+t5d5∗+t6d6∗U1−θri1′gb6−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗U1−θri1′gb6−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗gμ1b1+μ2b2+μ3b3−θri1′gd4∗−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗gμ1d5∗+μ2d6∗+μ3d2∗−θri1′gd4∗−ri2σ=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗g−θμ3ri1′d2∗−μ1θri1′d5∗−μ2θri1′d6∗g−ri2σd4∗=gri1θd1∗+ri2σd3∗+t5d5∗+t6d6∗g−ri1θd2∗−ri2σd4∗−μ1θri1′d5∗−μ2θri1′d6∗=gri1θd1∗−ri1θd2∗+ri2σd3∗−ri2σd4∗+t5′d5∗+t6′d6∗,where t5′=t5−μ1θri1′ and t6′=t6−μ2θri1′, for i=1,…,n.
Finally,D sends PP,PK=Z,gd1,gd2,gd3,gd4 to adversary A.
Query. SinceD knows all SKi, it can perfectly answer corruption queries and signing queries.
A produces a forgery signature M∗,S∗. Firstly, D must check that Verify PK,M∗,S∗ = “true”; if not, then D will abort. In addition, D must verify that it has not received a Type II forgery signature. To do this, D can check whether eℓgd5gd6,S1∗=1GT or not. If not, the forgery signature M∗,S∗ is a Type II signature; then D will abort. Notice that D needs the output of A to be a Type I forgery signature in order to defeat the subspace assumption with k=1 and l=6. Finally, D uses the forgery signature to determine what subspace T1 is in. D can simply check whether eℓS1∗,T1=1GT or not. If so, T1=gτ1ηb1∗+τ2βb2∗. Otherwise, T1=gτ1ηb1∗+τ2βb2∗+τ3b3∗.
It comes thatA ’s advantage is thus negligible if the subspace assumption with k=1 and l=6 holds.
According to Claims 1, 2, and 3, the signature schemeΦ is EUF-aCMA-DCA secure.


## 6. Comparison

Now, let us proceed to compare our scheme to other related schemes. As a reference for a further efficiency discussion, we have chosen the Libert-Yung (LY) signature scheme [10] and the second signature scheme in [15]. Let us denote the computational cost needed to perform a single bilinear pairing by e and the cost of a single modular exponentiation by E. Recall that the cost eN of a single bilinear pairing of composite order N=p1p2p3 is about 50 times more expensive than the cost ep of a single bilinear pairing of prime order p [12]. In general, in terms of computational overhead, a single bilinear pairing is equivalent to four modular exponentiations (or e≈4E). The first column in Table 1 provides the name of signature (LY13, LJY16, and ours). Other columns detail the computational costs needed to set up signature scheme (Setup), generate shares of signature (Share-Sign), verify shares (Share-Verify), combine shares into a signature (Combine), and verify a signature (Verify).Table 1
Comparison of efficiency.
SchemeSetupShare-signShare-verifyCombineVerifyLY13 [10]50n+1e+nE3E100e+E2tE150e+ELJY16 [15]t2+5t+7E2lE+18E10e+2lE8t+1E10e+2lEOurs7e+36E13E6e+2E06e+Ee denotes a single bilinear pairing, E denotes a single modular exponentiation, l denotes the length of the block message, and n denotes the number of the participants.In [15], the scheme mainly uses Groth-Sahai’s [17] proof systems technique, but our scheme mainly uses dual pairing vector spaces (DPVS) technique. The main difference of these two techniques is that the DPVS technique can effectively reduce computational complexity at the cost of slightly increasing storage space.


## 7. Conclusion

In this paper, we have proposed an efficientt,n threshold signature scheme. Under the subspace assumption, we have proven that our scheme is secure against existential forgeries under adaptive chosen message attacks and adaptive corruption attacks in the standard model. Our scheme is more efficient than the LY13’s and LJY16’s threshold signature schemes.



---

*Source: 6697295-2021-03-09.xml*