Introducing The 2-of-3 Threshold Signature Protocol by GG18
A threshold signature is a fair authorization method. The authorization can take effect only when the number of authorizations reaches the threshold value. The threshold signature scheme introduced in this blog does not need to introduce a trusted third party and takes the two-out-of-three threshold signature protocol as an example. And Eigen Network also open-sourced the multi-platform friendly TSS library here, try it out to understand this algorithm better.
Overview the solution
Consider an ECDSA signature algorithm that works over a cyclic group G of prime order q generated by an element g. It uses a hash function H defined from arbitrary strings into Zq.
The technical complication with sharing ECDSA signatures comes from having to jointly compute R (which requires raising g to the inverse of a secret value k) and to compute s which requires multiplying two secret values k, x.
The players start with a (t, n) Shamir sharing of the secret key x, which means there are n participants; when there are t+1 participants, the signature can be terminated successfully. Each player holds part of the private key 𝓌ᵢ. When t+1 players want to sign, they generate an additive sharing of two random values k = ∑ kᵢ and 𝛾 = ∑ 𝛾ᵢ and they use the idea of MtA (for Multiplicative to Additive) to compute additive sharing of the products 𝛿 = k𝛾 and 𝜎 = kx = k∑𝓌ᵢ. By multiplying the local shares of 𝛾 by the public value 𝛿⁻¹ the players end up with an additive sharing of k⁻¹.
1. Preliminary knowledge
1.1 Additively Homomorphic Encryption
Adopt Paillier’s cryptosystem that is additively homomorphic modulo a large integer N. Let Eₚₖ(∙) denote the encryption algorithm using public key pk. Given cipher-texts c₁=Eₚₖ(a) and c₂=Eₚₖ(b), there is an efficiently computable function ⊕such that c₁⊕c₂ = Eₚₖ(a+b mod N); Given an integer a∈N and a cipher-text c=Eₚₖ(m), there is a scalar multiplication operation denoted by ⊗ such that a⊗c = Eₚₖ(am mod N).
1.2 MtA (for Multiplicative to Additive)
Assume there are two parties Alice and Bob holding two secrets a, b ∈ Zq respectively which we can think of as multiplicative shares of a secret x = ab mod q.
1.3 Feldman’s VSS Protocol
In Shamir’s scheme, to share a secret σ∈Zq, the dealer generates a random degree t polynomial p(∙) over Zq such that p(0)=σ. The secret shares are evaluations of the polynomial
Each player Pᵢ receives a share σᵢ=p(i) mod q. In a verifiable secret-sharing scheme, the auxiliary information is published that allows players to check that their shares are consistent and define a unique secret. Feldman’s VSS is an extension of Shamir Secret Sharing.
1.4 Zero-Knowledge
It is equivalent to a challenge-response mechanism. If you answer correctly, you can prove that you know the secret. More detail can be found in our previous blog.
1.5 Non-Malleable Equivocable Commitments[2]
Com is the commitment algorithm. On input pk (the public key associated with the commitment scheme) and a message M, it outputs [C(M), D(M)] = Com(pk, M, R) where r are the coin tosses.
Ver is the verification algorithm. On input C, D and pk it either outputs a message M. If [C(M), D(M)] = Com(pk, M, R) then Ver(pk, C(M), D(M)) = M. For every message pair M, M’, the distributions C(M) and C(M’) are statistically close.
The sender publishes a commitment C(M), and then he will send D(M) to the receiver. C(M) is the commitment string, while D(M) is the de-commitment string, which is kept secret until opening. The receiver will be convinced that the sender did not ”change his mind.”
2. The 2-of-3 Threshold ECDSA
2.1 Key Generate Protocol
Phase 1.
Each Player Pᵢ selects uᵢ ∈Zq; computes [KGCᵢ, KGDᵢ]=Com(uᵢ∙G) and broadcasts KGCᵢ; Each Player Pᵢ broadcasts Eᵢ the public key for Paillier’s cryptosystem.
Phase 2.
Each Player Pᵢ broadcasts KGDᵢ and de-committed it, obtaining the value Uᵢ ( Uᵢ=uᵢ∙G ). All three parties calculate the public key PK=U₁+U₂+U₃ and the private key is sk = x = u₁+u₂+u₃(unknown to all three parties).
Using Feldman-VSS Protocol, Each Player Pᵢ constructs a polynomial of degree one: pᵢ(x)=uᵢ+aᵢx ( aᵢ→$Zp ) that for different secret value aᵢ. See the figure for details.
At this time, all three users have three shards of public key X₁, X₂, X₃. Using the Lagrange interpolation coefficient method, any two players can recover the complete public key. At the same time, any two players can recover the complete secret key.
Phase 3.
At this phase, players need to prove that they know the shard private key xᵢ through zero-knowledge proof. At the same time, the players should prove that they know the private key corresponding to the public key Eᵢ provided in phase 1. According to Paillier’s cryptosystem algorithm, Nᵢ=pᵢqᵢ is the RSA modulus associated with Eᵢ, which means using zero-knowledge proof of knowing the pᵢ and qᵢ value can finish the proof.
2.2 The 2-of-3 Threshold ECDSA Signature Protocol
Take Player 1 and Player 2 as examples to sign the data, where 𝓌ᵢ is the additive component of the private key (obtained in 2.1Phase 2).
Phase 1.
Each Player Pᵢ select kᵢ, 𝛾ᵢ ∈Zq; computes [Cᵢ, Dᵢ]=Com( 𝛾ᵢ∙G) and broadcasts Cᵢ( i=1,2 ). Define k=k₁+k₂, 𝛾=𝛾₁+𝛾₂, and the secret key is: sk=x=𝓌₁+𝓌₂. Note that
Phase 2.
P₁ and P₂ run MtA with shares kᵢ, 𝛾ᵢ respectively. After that operation, P₁ can get the value k₁𝛾₂, k₁𝓌₂; and P₂ can get the value k₂𝛾₁, k₂𝓌₁.
Phase 3.
Every player Pᵢ broadcasts δᵢ and the players reconstruct δ = δ₁+δ₂ = k𝛾. The players compute δ⁻¹ mod q.
Phase 4.
Each Player Pᵢ broadcasts Dᵢ and de-committed it, obtaining the value Γᵢ ( Γᵢ=𝛾ᵢ∙G ). P₁ and P₂ need to prove that they know the value of 𝛾₁ and 𝛾₂ through zero-knowledge proof. Therefore, both player 1 and player 2 can calculate the R value in ECDSA.
Phase 5.
Each player Pᵢ sets sᵢ = mkᵢ + rσᵢ. Note that
Because s₁ and s₂ are the additive shares of s, the player does not broadcast directly. The additive shares of s should broadcast after two rounds of commitment, opening, and verification and then verify the complete signature’s correctness. The whole protocol can be described as below.
Closing
In sum, the GG18 uses VSS to generate the shared key, and then compute the final signature using MtA algorithm. We’ll reveal the signing performance data in the next step.
Again, Eigen Network also open-sourced the multi-platform friendly TSS library here, try it out to understand this algorithm better. And feel free to join us to build a more private and secure transaction ecosystem.
Reference
[1] GG18: https://eprint.iacr.org/2019/114.pdf
