Dive Into Two-Party Signature Protocol
ECDSA is a standard digital signature scheme that is widely used in TLS, Bitcoin, and elsewhere. Unlike other schemes like RSA, Schnorr signatures, and more, it is particularly hard to construct efficient threshold signature protocols for ECDSA (and DSA). As a result, the best-known protocols today for secure distributed ECDSA require running heavy zero-knowledge proofs and computing many large-modulus exponentiations for every signing operation. The following protocol is proposed by Yehuda Lindell, which considers the specific case of two parties (and thus no honest majority). It’s approximately two orders of magnitude faster than the previous best.
1. Preliminary knowledge
1.1 Sigma Zero-knowledge Proof Protocol
Let G be a group of order q, with generator g. P and V have public input h∈G, P has ω such that h=ω⋅G, and execute the protocol below.
- P selects a random number r, calculates a=r⋅G, and sends a to V
- V selects a random number e and sends e to P
- P calculates z=r+e⋅ω and sends z to V
- V verifies, if the equation z⋅G=a+e⋅H holds, accept, otherwise reject
More detail can be found in our previous blog.
1.2 Diffie-Hellman Key Exchange protocol
Assume Alice has a private key sk₁=α and a public key PK₁=α⋅G. Bob has a private key sk₂=β and a public key PK₂=β⋅G.
Protocol:
Alice sends her public key PK₁ to Bob; Bob sends his public key PK₂ to Alice.
Alice calculates PK₂^{sk₁}=(β⋅G)⋅α={αβ}⋅G; Bob calculates PK₁^{sk₂}=(α⋅G)⋅β={αβ}⋅G.So Alice and Bob calculate the same session key Key={αβ}⋅G, or Key=Hash({αβ}⋅G)
1.3 Paillier Homomorphic Encryption
Key generation: Generate two large prime numbers p, q with the same length and satisfy gcd(pq, (p-1)(q-1))=1. Calculate n:=pq, λ:=lcm(p-1, q-1); define fractional division function L(y)=L(y-1)/n; choose a positive integer g∈ Z_{n²} so that μ=(L(g^λ mod n²))⁻¹ exists. The public key is (n, g), and the private key is (λ, μ).
Encrypt: Define message m∈ Zₙ, choose a random number r∈ Zₙ, calculate the ciphertext c:=gᵐ⋅ rⁿ mod n²
Decrypt: Enter ciphertext c∈ Z_{n²}, calculate the plaintext:
Homomorphism: Given two ciphertexts c₁, c₂∈ Z_{n²}, c₁=Encₚₖ(m₁), c2=Encₚₖ(m₂)
- Define the addition operation between ciphertexts⊕: c₁⊕ c₂=c₁c₂mod n², therefore, c₁⊕ c₂=c₁c₂mod n²=Encₚₖ(m₁+m₂ mod n)
- Given a∈ Zₙ, c=Encₚₖ(m), define the multiplication operation of plaintext and ciphertext ⨂: a⨂c=cᵃ mod n²=Encₚₖ(am mod n)
1.4 ECDSA
Initialization: The elliptic curve generator is G, the scalar domain is Fᵣ, and the base domain is F_q.
Key generation: Input security parameters, output private key x∈ Fᵣ and public key PK, and satisfy the following discrete logarithmic relationship
- PK=x⋅ G
- PK=x₁x₂⋅ G
Signature: Input any message M, calculate m:=Hash(M); select a one-time random number k∈ Fᵣ, calculate R:=k⋅G, take the abscissa R as r:=Rₓ mod|Fᵣ|; calculate s:=k⁻¹(m+xr)=(k⁻¹m+k⁻¹xr)mod|Fᵣ|, then the signature is (r,s).
Validation: Input message M, calculate m:=Hash(M); check r,s∈ Fᵣ, calculate R’:=(s⁻¹m)⋅ G+(s⁻¹r)⋅ PK, take the abscissa R’ as r’:=R’ₓ mod|Fᵣ|; check r=r’. If equal, accept, otherwise reject.
The formula derivation process is as follows:
The verification essence of ECDSA:
The signer constructs a linear relationship s := k^{-1}×(m + xr) on the scalar field.
The verifier reconstructs the linear relationship R = s^{-1}×m × G + s^{-1}×r × PK on the elliptic curve points. The linear relationship is reconstructed successfully, but the private key x and random number k are unknown.
2. The Two-party ECDSA
In order to lead the final solution step by step, let’s review the signature formula of ECDSA again.
s := k⁻¹(m+xr) = (k⁻¹m+k⁻¹xr)mod|Fᵣ|
Firstly, let’s run a multiplicative share to calculate the x and k.
The two parties hold x₁, x₂, such that x = x₁ · x₂.
The two parties choose k₁, k₂, define k = k₁ · k₂, and R = k · G.
After this, each party can locally compute an inverse of their portion of k, and so hold shares of k^{-1} = k₁^{-1} · k₂ ^{-1}.
By far, the parties have r and shares k₁, x₁, and k₂, x₂ respectively.
But the difficulty is computing s because we don’t have additive shares. So the protocol uses the homomorphic encryption scheme in order to finish this computation.
We have introduced the Paillier encryption scheme with homomorphism. And with the Paillier encryption scheme, Party P_1 generates a Paillier key pair and sends Enc(k₁^{-1} · m) and Enc(k₁^{-1} · x₁· r) with Paillier to P_2.
And Party P_2 can use homomorphic properties to compute:
- Enc(k₂ ^{-1} · k₁^{-1} · m) — scalar multiplication
- Enc((k₂ ^{-1} · x₂) · k₁^{-1} · x₁· r) — scalar multiplication
- The sum s = Enc(k⁻¹m+k⁻¹xr) — additive homomorphism
Then P_2 sends the encrypted s to P_1 and P_1 decrypts and obtains the signature.
Here we see that by using Paillier’s homomorphism, we solve the difficulty of computing s due to the lack of additive shares.
Next, let’s talk about security under malicious adversaries. The parties need to prove correctness:
- P_1 needs to prove that the encryptions contain k₁^{-1}. This is hard since P_2 only has R₁=k₁⋅ G.
We need zero-knowledge proofs to ensure security and the zero-knowledge proofs make the above protocol very expensive.
Let’s move on and see what the protocol we focus on today optimizes to make things better.
We assume that P_1 and P_2 still hold multiplicative shares x₁, x₂ of x, and P_2 has encryption of x₁ under P_1’s Paillier public key.
Firstly, the two parties run a “simulatable” Diffie-Hellman key exchange to compute R = k₁⋅ k₂ · G.
- P_1 sends a commitment to R₁=k₁⋅ G to P_2 and a ZK proof of discrete logarithm
- P_2 sends R₂=k₂⋅ G to P_1 and a ZK proof of discrete logarithm
- P_1 decommits
By far, P_2 has R, x₂, k₂(and also k₂^{-1}), as well as c = Enc(x₁).
P_2 can compute c’= Enc(s’) = Enc(k₂^{-1} · m) + Enc((k₂ ^{-1} · r · x₂) · x₁) with the homomorphic properties of encryption.And note that the real signature is just k₁^{-1} · s’.
And then P_2 sends c’ to P_1, P_1 just decrypts c’ and computes s = k₁^{-1} · s’ and verifies.
The above is the basic framework of the protocol. We divide the protocol process into two steps, namely the key generation protocol and the signature protocol.
2.1 Two-Party Key Generate Protocol
step 1: User₁
1. Select a random number x₁∈ F_{r/3}, calculate Q₁=x₁⋅ G
2. Generate a zero-knowledge proof proof₁=ZK{x₁|Q₁=x₁⋅ G} for a secret random number x₁
3. Generate commitment and opening commitment [KGC₁, KGD₁]=Com(Q₁, proof₁) for Q₁ and proof₁
4. Send commitment KGC₁ to User₂
step 2: User₂
1. Receive commitment KGC₁ from User₁
2. Select a random number x₂∈ Fᵣ, calculate Q₂=x₂⋅ G
3. Generate a zero-knowledge proof proof₂=ZK{x₂|Q₂=x₂⋅ G} for a secret constant x₂
4. Send proof₂, Q₂ to User₁
step 3: User₁
1. Receive proof₂ from User_2, check to obtain Q₂;
2. Send opening commitments KGD₁ to User_2
3. Generate the Paillier cipher public and private keys (pk, sk), the length is max{3log|r|+1, n}, and calculate the Paillier homomorphic encryption c_{key}:=Encₚₖ(x₁) (to prepare for the homomorphic calculation of the signature).
4. Generate a zero-knowledge proof proof_{Paillier, 1}=ZK{sk|pk=N=p₁⋅ p₂} of sk and send proof_{Paillier, 1} to User_2
5. Send c_{key} to User₂
step 4: User₁
1. Generate a zero-knowledge proof proof_{Paillier, 2} and send it to User₂. More specifically, this step yields a proof to prove in zero-knowledge that a value encrypted in a given Paillier ciphertext is the discrete log of a given Elliptic curve point.
step 5: User₂
1. Obtain the opening commitment KGD₁ from User_1, thereby obtaining Q₁ and proof₁, verifying the validity
2. Obtain proof_{Paillier, 1} from User_1 to verify the validity
3. Obtain proof_{Paillier, 2} from User₁ to verify the validity
4. Check the length of pk is max{3log|r|+1, n}
step 6: The public key is Q， and both users can calculate it.
- Calculate Diffie-Hellman public key Q=x₁⋅ Q₂, store (x₁, Q)
- Calculate Diffie-Hellman public key Q=x₂⋅ Q₁, store (x₂, Q, c_{key})
The public key is made public and becomes their public key Q=x₁x₂⋅ G.
The private key sk = x₁x₂ does not appear.
2.2 Two-Party Signature Protocol
The message that both parties need to sign is m’=Hash(m)mod|Fᵣ|.
step 1: User₁
1. Select a one-time random number k₁∈ Fᵣ, calculate R₁=k₁⋅ G
2. Generate a zero-knowledge proof proof₁=ZK{k₁|R₁=k₁⋅ G} for secret knowledge k₁
3. Generating commitments and opening commitments [KGC₁,KGD₁]=Com(R₁, proof₁) for R₁ and proof₁
4. Send commitments KGC₁ to User₂
step 2: User₂
1. Receive commitments KGC₁ from User₁
2. Select a random number k₂∈ Fᵣ, calculate R₂=k₂⋅ G
3. Generate a zero-knowledge proof proof₂=ZK{k₂|R₂=k₂⋅ G} for a secret constant k₂
4. Send proof₂, R₂ to User₁
step 3: User₁
1. Receive proof₂, R₂ from User₂, verify and obtain R₂
2. Send opening commitments KGD₁ to User_2
step 4: User₂
- Receive the open commitments KGD₁ from User_1, obtain R₁ and proof₁, and check its validity;
- Calculate Diffie-Hellman one-time public random point R:=k₂⋅ R₁, parse (r_x, r_y):=R, calculate r:=r_x mod|Fᵣ|;
- Select random number ρ ∈ Z_{F²ᵣ}, calculate the Paillier homomorphic encryption c₁:=Encₚₖ(ρ ⋅ |Fᵣ|+[k₂^(-1)⋅ m’ mod |Fᵣ|]), and calculate v:=k₂^(-1)⋅ r⋅ x₂ mod|F₂|, c₂:=v⊕ c_{key}, c₃:=c₁⊕ c₂;
4. Send c₃ to User₁
step 5: User₁ outputs signature
- Calculate the Diffie-Hellman one-time public random point R:=k₁⋅ R₂, parse (rₓ, r_y):=R, calculate (r, bool):=rₓ mod|Fᵣ|
- Paillier decrypts c₃, obtains s’=Decₛₖ(cₑ), calculates s’’=k^(-1)₁⋅ s’ mod|Fᵣ|. let s=min{s’’, |Fᵣ|-s’’}
3. Verify the correctness of the signature (m’, (r, s), Q).
Closing
The Lin17 protocol is widely used by MPC wallets, like ZengoX. It leverages ZKP and ECDH to convince the peer to calculate the final signature. In the next post, we will introduce the multi-party ECDSA protocols, different from 2P ECDSA, it uses secret share to allow multi-parties to keep custodial of the key’s share, and generate the signature collaboratively.
