Two-Party ECDSA

Open Table of contents

What it is
How it works
Why it works
References

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/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 $E$ that is of order $q$ and has a generator $G$ . All calculations are done $\bmod\ q$ if not stated otherwise.

Note: Parameters generated by Alice will use the subscript $_1$ while for Bob’s parameters we’ll use the subscript $_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 $\mathbb{Z}_q$ while the public keys are derived by multiplying the private key with the generator $G$ .

Alice computes:

a \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

A = aG

While Bob computes:

b \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

B = bG

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

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

As a next step, both Alice and Bob use their private- and public keys to derive a shared public key $X$ 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:

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

Whereas Bob calculates:

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

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

Alice calculates:

k_1 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

R_1 = k_1G

Bob does the same:

k_2 \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_q

R_2 = k_2G

The $R_1$ and $R_2$ values are then exchanged and used to derive a shared, random point $R$ by multiplying the other’s $R$ value with the local nonce $k$ . Deriving this shared $R$ value follows the same Elliptic Curve Diffie-Hellman protocol that was used to agree on the $X$ value.

In this case Alice calculates:

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

And Bob computes:

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

Given that the shared, random $R$ value is a point on the Elliptic Curve it has an $x$ - and $y$ -coordinate. We can therefore define a value $r$ as the $x$ -coordinate of $R$ :

r = R_x

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

z = H(m)

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

In the following, Bob will use the Paillier Cryptosystem to incorporate Alice’s and his private key into the signature. The Paillier Cryptosystem works with a different modulus compared to the modulus $q$ that’s used for our Elliptic Curve calculations.

To ensure that no information gets leaked to Alice, Bob randomly samples a large value $p$ :

p \overset{{\scriptscriptstyle\$}}{\leftarrow} \mathbb{Z}_{q^2}

This value is then multiplied by $q$ and added to the value inside of the encryption. Given that all calculations are done $\bmod\ q$ , the $pq$ will cancel out in subsequent operations.

The first ciphertext $c_1$ that Bob calculates is the encryption of $k_2^{-1}z + pq$ under Alice’s Paillier public key:

c_1 = enc(k_2^{-1}z + pq)

Next up, he derives the constant $y$ :

y = k_2^{-1}rb

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

\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” $s'$ by multiplying both ciphertexts $c_1$ and $c_2$ .

\begin{aligned} s' &= c_1c_2 \\ &= enc(k_2^{-1}z + pq)enc(ak_2^{-1}rb) \\ &= enc(k_2^{-1}z + pq + k_2^{-1}rab) \\ &= enc(k_2^{-1}(z + rab) + pq) \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 $s'$ with Alice.

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

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

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

To verify the signature Alice and Bob generated, the verifier recomputes $z$ as $z = H(m)$ . Furthermore the values $u$ , $v$ and $R$ need to be calculated as follows:

u = s^{-1}z

v = s^{-1}r

R = uG + vX

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

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

Two-Party ECDSA

Why it works

The first thing to note is that while Alice and Bob derive a shared public key $X$ , they don’t know each other’s private keys $a$ and $b$ . In fact Bob only get’s access to Alice’s encrypted version of her private key ( $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 $s'$ that incorporates information about both of their private keys $a$ and $b$ without disclosing them.

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

dec(s') = k_2^{-1}(z + rab) + pq

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 $z$ is the hash of the message $m$ which in turn is interpreted as a point on the Elliptic Curve $E$ .

We can then use the $s$ value of the signature to isolate the multiplication of both $k$ values (Remember that $pq$ will cancel out given that all calculations are done $\bmod\ q$ ):

\begin{aligned} s &= k_1^{-1}k_2^{-1}(z + rab) + \cancel{pq} && \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 $R$ and substituting $k_1k_2$ for $s^{-1}(z + rab)$ (as we’ve just calculated), we can see that $R = k_1k_2G$ :

\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 $R$ is the same as the one Alice and Bob derived from their individual $k$ and $R$ values.

This implies that its $x$ -coordinate is equal to the $r$ value of the signature. The signature over the message $m$ is therefore valid.

References

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.