Skip to content

Two-Party ECDSA

Table of contents

Open Table of contents

What it is

Two-Party ECDSA (2P-ECDSA) is a protocol that allows two entities to jointly create digital signatures over arbitrary messages via a shared private key that neither of the participants has full access to or control over.

Conceptually 2P-ECDSA is a 2/22/2 threshold signature scheme that only creates a valid signature if both protocol participants collaborate.

How it works

Note: The 2P-ECDSA protocol described here is a simplified version of Yehuda Lindell’s ”Fast Secure Two-Party ECDSA Signing” construction which in turn uses the Paillier Cryptosystem and its additive homomorphic properties.

We won’t go into the full details of the Paillier Cryptosystem in this writeup. However there’ll be explanations when necessary to aid understanding.

Before continuing, it’s useful to have a good understanding of the Elliptic Curve Digital Signature Algorithm (ECDSA) for which you can find an in-depth explanation in my ECDSA blog post.

In our example we assume that Alice and Bob are the two protocol participants that agree on a shared private key (that neither Alice, nor Bob knows) which will be used to sign a message collaboratively.

This signed message can then be verified by a third party via the regular ECDSA signature verification algorithm.

We’ll work with an Elliptic Curve EE that is of order qq and has a generator GG. All calculations are done mod q\bmod\ q if not stated otherwise.

Note: Parameters generated by Alice will use the subscript 1_1 while for Bob’s parameters we’ll use the subscript 2_2.

The first step is for Alice and Bob to generate their private- and public keys. The private keys are created by sampling a random value from Zq\mathbb{Z}_q while the public keys are derived by multiplying the private key with the generator GG.

Alice computes:

a$Zqa \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q A=aGA = aG

While Bob computes:

b$Zqb \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q B=bGB = bG

Alice also generates a private- and public key pair for the Paillier Cryptosystem and encrypts her private key aa under her Paillier public key which we’ll denote as enc(a)enc(a).

Alice now shares her public key AA, her Paillier public key as well as her encrypted private key enc(a)enc(a) with Bob. Bob in turn sends his public key BB to Alice.

As a next step, both Alice and Bob use their private- and public keys to derive a shared public key XX via a protocol that’s called Elliptic Curve Diffie-Hellman. This is done by multiplying the private key with the other participant’s public key.

In Alice’s case, she computes:

X=aB=abG\begin{aligned} X &= aB \\ &= abG \end{aligned}

Whereas Bob calculates:

X=bA=baG\begin{aligned} X &= bA \\ &= baG \end{aligned}

Next up, Alice and Bob both need to separately sample another, random value kk from Zq\mathbb{Z}_q. This value is called the “nonce” (number used once) and should never be reused. The nonce kk is then multiplied by the generator GG to derive the value RR which is a point on the Elliptic Curve EE.

Alice calculates:

k1$Zqk_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R1=k1GR_1 = k_1G

Bob does the same:

k2$Zqk_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q R2=k2GR_2 = k_2G

The R1R_1 and R2R_2 values are then exchanged and used to derive a shared, random point RR by multiplying the other’s RR value with the local nonce kk. Deriving this shared RR value follows the same Elliptic Curve Diffie-Hellman protocol that was used to agree on the XX value.

In this case Alice calculates:

R=k1R2=k1k2G\begin{aligned} R &= k_1R_2 \\ &= k_1k_2G \end{aligned}

And Bob computes:

R=k2R1=k2k1G\begin{aligned} R &= k_2R_1 \\ &= k_2k_1G \end{aligned}

Given that the shared, random RR value is a point on the Elliptic Curve it has an xx- and yy-coordinate. We can therefore define a value rr as the xx-coordinate of RR:

r=Rxr = R_x

In our example Alice initiates the signature so she needs to turn her message mm into a representation that can be “mapped onto” the Elliptic Curve EE. She does this by hashing mm via a cryptographic hash function HH, the result of which can be interpreted as a point on the curve:

z=H(m)z = H(m)

This zz value is then sent to Bob who uses it to generate a partial signature.

Bob does this by first calculating a ciphertext c1c_1 as the encryption of k21zk_2^{-1}z under Alice’s Paillier public key:

c1=enc(k21z)c_1 = enc(k_2^{-1}z)

Next up, he derives the constant yy:

y=k21rby = k_2^{-1}rb

The value yy is then used to calculate another ciphertext c2c_2 in which Bob uses Alice’s encrypted private key (remember that Alice sent enc(a)enc(a) in the beginning of the protocol) to raise it to the power of yy.

c2=enc(a)y=enc(ay)=enc(ak21rb)\begin{aligned} c_2 &= enc(a)^{y} \\ &= enc(ay) \\ &= enc(ak_2^{-1}rb) \end{aligned}

In Paillier’s Cryptosystem, a ciphertext raised to a constant will decrypt to the product of the plaintext and the constant.

Finally, Bob calculates an “almost signature” ss' by multiplying both ciphertexts c1c_1 and c2c_2.

s=c1c2=enc(k21z)enc(ak21rb)=enc(k21z+k21rab)=enc(k21(z+rab))\begin{aligned} s' &= c_1c_2 \\ &= enc(k_2^{-1}z)enc(ak_2^{-1}rb) \\ &= enc(k_2^{-1}z + k_2^{-1}rab) \\ &= enc(k_2^{-1}(z + rab)) \end{aligned}

In Paillier’s Cryptosystem, the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts.

Bob now shares this partial signature ss' with Alice.

Finally Alice can turn ss' into a valid ss by multiplying the decryption of ss' with k11k_1^{-1}:

s=k11dec(s)=k11k21(z+rab)\begin{aligned} s &= k_1^{-1}dec(s') \\ &= k_1^{-1}k_2^{-1}(z + rab) \end{aligned}

The signature for the message mm is the tuple (r,s)(r, s) which Alice can send alongside the shared public key XX to a third party for verification.

To verify the signature Alice and Bob generated, the verifier recomputes zz as z=H(m)z = H(m). Furthermore the values uu, vv and RR need to be calculated as follows:

u=s1zu = s^{-1}z v=s1rv = s^{-1}r R=uG+vXR = uG + vX

The signature is valid if r=?Rxr \overset{?}{=} R_x.

That is, if the rr value from the signature equals the xx-coordinate of Alice’s and Bob’s shared Elliptic Curve point RR that the verifier calculated as R=uG+vXR = uG + vX.

Two-Party ECDSA

Why it works

The first thing to note is that while Alice and Bob derive a shared public key XX, they don’t know each other’s private keys aa and bb. In fact Bob only get’s access to Alice’s encrypted version of her private key (enc(a)enc(a)) which is encrypted via the Paillier Cryptosystem.

By utilizing the additive homomorphic properties of Paillier’s Cryptosystem, Bob can still calculate a partial signature ss' that incorporates information about both of their private keys aa and bb without disclosing them.

In fact, even once Alice decrypts the partial signature ss' she doesn’t learn anything about either private key as they’re “masked” by multiplying them with the shared rr value and adding the hashed message zz to it:

dec(s)=z+rabdec(s') = z + rab

The signature verification algorithm is exactly the same as the one that’s used in standard ECDSA, which means that a signature generated via 2P-ECDSA looks and behaves like a regular ECDSA signature.

Let’s use some regular algebra to convince ourselves that the signature verification works.

First, we should recall that zz is the hash of the message mm which in turn is interpreted as a point on the Elliptic Curve EE.

We can then use the ss value of the signature to isolate the multiplication of both kk values:

s=k11k21(z+rab)×k1×k2sk1k2=z+rab×s1k1k2=s1(z+rab)\begin{aligned} s &= k_1^{-1}k_2^{-1}(z + rab) && \mid \times k_1 \times k_2 \\ sk_1k_2 &= z + rab && \mid \times s^{-1} \\ k_1k_2 &= s^{-1}(z + rab) \end{aligned}

By expanding RR and substituting k1k2k_1k_2 for s1(z+rab)s^{-1}(z + rab) (as we’ve just calculated), we can see that R=k1k2GR = k_1k_2G:

R=uG+vX=uG+vabG=G(u+vab)=G(s1z+s1rab)=s1G(z+rab)k1k2=s1(z+rab)=k1k2G\begin{aligned} R &= uG + vX \\ &= uG + vabG \\ &= G(u + vab) \\ &= G(s^{-1}z + s^{-1}rab) \\ &= s^{-1}G(z + rab) && \mid k_1k_2 = s^{-1}(z + rab) \\ &= k_1k_2G \end{aligned}

Checking this against the signature creation process we’ve described above, we can verify that this Elliptic Curve point RR is the same as the one Alice and Bob derived from their individual kk and RR values.

This implies that its xx-coordinate is equal to the rr value of the signature. The signature over the message mm is therefore valid.


The following resources have been invaluable for me to learn the concepts discussed in this article.

You should definitely give them a read if you want to dive deeper into the topic.