Efficient Secure Two Party ECDSA

Abstract

Distributing the Elliptic Curve Digital Signature Algorithm (ECDSA) has received increased attention in past years due to the wide range of applications that can benefit from this, particularly after the popularity that the blockchain technology has gained. Many schemes have been proposed in the literature to improve the efficiency of multiparty ECDSA. Most of these schemes either require heavy homomorphic encryption computation or multiple executions of a functionality that transforms Multiplicative shares to Additive shares (MtA). Xue et al. (CCS 2021) proposed a 2-party ECDSA protocol secure against malicious adversaries and only requires one execution of MtA, with an online phase that consists of only one party sending one field element to the other party with a computational overhead dominated by the verification step of the signature scheme. We propose a novel protocol, based on the assumption that the Computational Diffie-Hellman problem is hard, that offers the same online phase performance as the protocol of Xue et al., but improves the offline phase by reducing the computational cost by one elliptic curve multiplication and the communication cost by two field elements. To the best of our knowledge, our protocol offers the most efficient offline phase for a two-party ECDSA protocol with such an efficient online phase.

Y.T. Alaoui—Most of the work done while at imec-COSIC, KU Leuven, Belgium.

1 Introduction

Multi-party computation (MPC) is a technique from cryptography that enables multiple parties to conduct computation on their secrets while preserving them private. MPC was formally introduced with Yao’s 2-party protocol for the Millionaires’ problem [26]. Today, it became a pioneering solution for a wide variety of real-world problems, such as cryptographic key protection, privacy-preserving data analytics, and so forth [15].

With the rise of the blockchain technology and cryptocurrencies, multi-party signing [7] and, in particular, threshold signing has gained significant attention in the past decade. Namely, a (t, n) signature scheme enables n parties to distribute the signing power in such a way that signing a message m requires the collaboration of at least $t+1$ of them. This is accomplished by having the n parties participate in the key generation phase to produce a private key unknown to them. At the end of this phase, each party will hold a share of the private key, together with the public key. Then the signing phase is executed as an interactive protocol as well, where at least $t+1$ parties participate with their shares so as to produce the signature, which is then checked with the verification algorithm of the signature scheme being distributed. This benefits cryptocurrencies as transactions are sent by producing a signature using the sender’s private key. Thus to prevent a single point of failure while maintaining the key, one can share it among different parties placed in different locations, who need to collaborate to sign.

In this regard, thresholdizing the ECDSA algorithm has drawn most of the attention, as it is the signing algorithm used in Bitcoin. We can find in the literature many works that addressed this [2, 5, 6, 8, 9, 12,13,14, 23, 25] where various schemes were constructed, either addressing the 2-party case [8, 13, 14, 25], or more generally, the n-party case [2, 5, 6, 9, 12, 23]; using generic MPC protocols [5, 23], or special purpose protocols targeting ECDSA [2, 6, 8, 9, 12,13,14, 25]. Those schemes differ particularly in the way of sharing values, namely additively or multiplicatively. That is, at the heart of the ECDSA algorithm, one needs to calculate $s = k^{-1}(H(m)+x \cdot r) \mod q$. In a threshold version of ECDSA, both the private key x and the random nonce k used for signing the message m are secretly shared among parties. In fact, to provide a threshold version of ECDSA, the main challenge consists of choosing an adequate way to secretly share k and x so that s can be computed efficiently. Note that this calculation contains inverting a secret, and multiplying it with another value obtained by evaluating linear operations over another secret (addition and multiplication with opened values).

For instance, for the 2-party case, additively secret sharing k is problematic for inversion, as in this case, party $\mathcal {P}_1$ holds $k_1$ and party $\mathcal {P}_2$ holds $k_2$ subject to $k_1+k_2=k \mod q$, and from this, the two parties need to calculate $k^{-1}$. Alternatively, one can secretly share k in a multiplicative way to overcome this obstacle, as in this case, inverting becomes a local operation; however, the resulting value still needs to be multiplied by $H(m)+x \cdot r$, which still introduces obstacles either x was additively or multiplicatively secret shared.

As a solution to these challenges, several authors in the field proposed using homomorphic encryption. This approach allows one party to transmit a secret to the other party in encrypted form so that they can execute the challenging computation and decrypt it afterward. The homomorphic encryption schemes that were used are partially homomorphic, as performing one type of operation over the ciphertexts was sufficient for the computation needed.

For the most part, homomorphic encryption was introduced to realize a Multiplicative-to-Additive (MtA) functionality which enables parties to obtain an additive version of the shares of a secret from a multiplicative one, adopting ideas from [17]. Based on this functionality, parties who hold multiplicative shares $\alpha$ and $\beta$, respectively, can get the corresponding additive shares a and b where $a+b=\alpha .\beta$ by querying this functionality. The need for querying this protocol arises when an additive sharing is preferable than a multiplicative one from a performance point of view. Of course, this functionality does not come for free, and it introduces a cost to the protocol whenever it is called; however, there exist many instantiations of it, such as Paillier encryption [20]-based MtA [12], El Gamal encryption [10]-based MtA [16], and Castagnos-Laguillaumie (CL) encryption [4]-based MtA [3]. Besides, one can also construct Oblivious Transfer (OT) [21]-based MtA [8], which has the advantage of decreasing the computational complexity by eliminating the need for homomorphic encryption at the expense of incurring a relatively high bandwidth. As a result, one has multiple options for MtA instantiations, each of which offers a different tradeoff between the computation and communication costs, thanks to which one can select the one that best fits the constraints faced. Also, it should be noted that Fireblocks’ teams showed a Paillier key vulnerability in [12] leaking secret key or inverse nonce information [18]. These attacks occur when the MtA functionality is used without range proofs that ensure the inputs of MtA are chosen from the required domain. Thus, it is recommended to use suitable range proofs to detect maliciously formed input in Paillier-based MtA functionality.

For the 2-party case of threshold ECDSA, two works are most related to ours, namely, the one of Lindell [14] and Xue et al. [25]. Lindell has proposed a simple and efficient 2-party protocol against malicious adversaries. To briefly go over this protocol, both x and k are secretly shared in a multiplicative way, where each party $\mathcal {P}_i$ generates $x_i$ in the key generation phase so that the private key x is equal to $x = x_1 \cdot x_2$. Party $\mathcal {P}_1$ also encrypts $x_1$ so as to send it to $\mathcal {P}_2$, then in the signing phase, the two parties generate their share of the nonce k, then $\mathcal {P}_2$ computes its share of s and sends it to $\mathcal {P}_1$, which involves encrypting and performing homomorphic encryption operations. Finally, $\mathcal {P}_1$ calculates the signature s, which involves decryption before the verification step.

On the other hand, Xue et al. proposed an online-friendly algorithm against malicious adversaries. That is, this protocol has a nearly optimal online phase, in the sense that the heaviest part of it consists of the verification step of the signature, which in turn consists of calculating two scalar multiplications M of elliptic curve points (scalar multiplications will be denoted as M from now on). The communication cost is also efficient, as only a single field element needs to be sent. This is opposed to [14] as one needs to send and operate over ciphertexts during the online phase. However, providing such an efficient online phase came with the cost of offloading all the heavy computation in the offline phase of the signing step. That is, while the key generation does not involve any encryption, an MtA is being executed for every signature during the signing phase, which is still a good compromise as it reduces the number of calls to the MtA functionality compared to other schemes. Thus the resulting protocol offers an efficient online phase with a good overall cost. However, this scheme can be further optimized, as we will see in the next section.

1.1 Our Contribution

We present a protocol against malicious adversaries with a nearly optimal online phase as in [25], but with reduced computation and communication costs for the offline phase. That is, our key generation is the same as in [25], where we produce additive secret sharings of x ($\mathcal {P}_i$ generates $Q_i \leftarrow [x_i] \cdot P$, where P is a generator of the curve, and the public key is $Q \leftarrow Q_1 + Q_2$), and our online phase requires two scalar multiplication M as in [25]. However, our offline phase reduces the number of EC multiplications by one and the size of data communicated by two field elements.

The cost reduction is achieved by eliminating the additional step of re-sharing the secret x in [25], and basing the security of our protocol on the 1-Weak Diffie-Hellman problem, which is equivalent to the Computational Diffie-Hellman problem. That is, at the heart of the signing phase of the protocol of [25], x was re-shared between the two parties (following obvious notation) as $x=x'_1.(k_2+r_1)+x'_2$, where the nonce k is shared as $k=k_1(r_1+k_2)$, then the shares $x'_{1}$ and $k_2$ are the values forwarded to the MtA functionality.

Instead, we simplified the protocol by adopting a multiplicative sharing of k where it is unnecessary to perform a re-sharing step ($\mathcal {P}_i$ generates $R_i \leftarrow [k_i] \cdot P$ for P the generator of the curve, and the point R from which we take the x-coordinate r is $R \leftarrow [k_1 \cdot k_2] \cdot P$). We query the MtA only once on the most convenient inputs for our choices. Namely, querying the MtA on $x_1$ as the input of $\mathcal {P}_1$, and $k^{-1}_2$ as the input of $\mathcal {P}_2$. This was a logical choice as holding an additive sharing as

$$\begin{aligned} x_1 \cdot k^{-1}_2 = a + b \mod q \end{aligned}$$

by the players allows them to do the online phase in only one pass, as the signature s can be written as

$$\begin{aligned} s=k_1^{-1} \cdot (k_2^{-1} \cdot (H(m) + x_2 \cdot r) + x_1 \cdot k^{-1}_2 \cdot r) \mod q \end{aligned}$$

In this case, $\mathcal {P}_2$ computes locally its signature share as

$$\begin{aligned} s_2 \leftarrow k_2^{-1} \cdot (H(m) + x_2 \cdot r) + b \cdot r \mod q \end{aligned}$$

and sends it to $\mathcal {P}_1$ to construct the signature

$$\begin{aligned} s \leftarrow k_1^{-1} \cdot (s_2 + a \cdot r) \mod q \end{aligned}$$

However, it is crucial to note that the protocol requires $\mathcal {P}_1$ to input $x_1$ for MtA. If there are no checks on this input to MtA, a malicious $\mathcal {P}_1$ can corrupt the system since $\mathcal {P}_1$ takes the partial signature $s_2$ and then generates the full signature s. For example, a malicious $\mathcal {P}_1$ can forge a signature on a different message $m'$ of his choice by crafting the value to be sent to MtA as $x'_1 \leftarrow -r^{-1} \cdot (H(m')-H(m)+x_1 \cdot r)$, then $\mathcal {P}_1$ will compute the full signature s as $k_1^{-1} \cdot (s_2+a \cdot r)=k_1^{-1} \cdot (k_2^{-1} \cdot (H(m)+x_2.r)+(a+b) \cdot r)=k^{-1} \cdot (H(m')+x \cdot r)$ which is a valid signature on $m'$ that is chosen by $\mathcal {P}_1$.

In order to prevent $\mathcal {P}_1$ from mounting such an attack and manipulating the distribution of $s_2$, we add a check operation on the correctness of the MtA input of $\mathcal {P}_1$. Namely after calling MtA and receiving its outputs, $\mathcal {P}_1$ computes $[a] \cdot P$ and sends it to $\mathcal {P}_2$, who computes $k_2 \cdot ([a] \cdot P+[b]\cdot P)$ and checks whether it is equal to $Q_1$ or not. The correctness of this equality ensures that $\mathcal {P}_1$ used the correct $x_1$ value as MtA input, and as we will see, $\mathcal {P}_1$ will not be able to bypass it, unless he breaks the standard assumption that the Computational Diffie-Hellman problem is hard. It is worth noting that the check we add is not concerned with the security of the underlying MtA, but rather to ensure that the parties involved are invoking the MtA with the appropriate inputs. This of course adds a round of communication to the protocol, however, it is a critical step in ensuring the protocol’s security, which is analogous to the consistency check executed immediately following the MtA call in [25].

In sum, the protocol we end up with utilized an additive sharing of x and a multiplicative sharing of k, which is a similar setting of [8] for the (1, n)-ECDSA case (i.e., any two parties among the n parties can construct a valid signature). However, we only call the MtA functionality once while it is being called three times in [8]. Besides, we only perform 13M, while 16M are needed for [8].

This improvement has an impact depending on the instantiation of MtA. For instance, in the case of an OT-based MTA, where such a choice is usually made to have a low computation cost, reducing the number of EC multiplications by one will decrease the computation cost of the offline phase of [25] (Table 4 of [25]) by 5.4%. On the other hand, in the case of a CL-based MtA, which introduces a low communication cost, reducing the size of transmitted data by two field elements decreases the communication cost of the offline phase of [25] (Table 5 of [25]) for the case of the secp256k1 curve by 3.7%. While these percentages may seem modest, the potential gains are substantial, given the vast scale at which ECDSA signatures are executed, and all the applications that can benefit from a distributed version of it.

We also implemented our protocol and obtained an online phase of 0.1 ms, which is half the time required for the online phase of [25]; however, given the similarity of the online phase between the two protocols, this difference in time is most likely due to our implementation’s use of the highly optimized C library secp256k1 for the operations over the curve.

1.2 Paper Organization

This paper is organized as follows: Sect. 2 provides the necessary background over the hardness assumption upon which we are basing the security of our protocol, the ECDSA scheme, and the ideal functionalities we used. Section 3 presents the proposed protocol, along with the cost analysis, comparison with related work, and its running time based on our implementation. Section 4 concludes the paper. Then in the Appendix, security proofs are given.

2 Preliminaries

2.1 Hardness Assumptions

The security of our protocol is based on the 1-Weak Diffie-Hellman problem [19], also referred to as the Inverse Diffie-Hellman problem [1]. That is, this problem is a special case of the k-Weak Diffie-Hellman problem (and can be proven to be equivalent to it), where the adversary is given a set of points $\{P$, $[x]{\cdot }P$, $[x^2]{\cdot }P,$ $\ldots ,$ $[x^k]{\cdot }P\}$ for a randomly chosen x, and asked to find $[x^{-1}]{\cdot } P$.

Definition 1

(Computational Diffie-Hellman Assumption.) Let $\mathbb {G}$ be a cyclic group of a large prime order, and P a generator of $\mathbb {G}$. Given a tuple (P, $[a]{\cdot }P$, $[b]{\cdot }P)$ for a randomly chosen a and b, it is computationally hard to compute $[a {\cdot } b] {\cdot } P$.

Definition 2

(1-Weak Diffie-Hellman Assumption.) Let $\mathbb {G}$ be a cyclic group of a large prime order, and P a generator of $\mathbb {G}$. Given a tuple (P, $[x]{\cdot }P)$ for a randomly chosen x, it is computationally hard to compute $[x^{-1}]{\cdot }P$.

Theorem 1

The 1-Weak Diffie-Hellman and the Computational Diffie-Hellman assumptions are equivalent.

The proof of theorem 1 is given Appendix A.

2.2 The ECDSA Scheme

The ECDSA scheme is a signature algorithm that involves key generation, signing, and verification. Let $\mathbb {G}$ be an elliptic curve group of order q of size $\lambda$ bits, with a generator P, and the neutral element being denoted as $\mathcal {O}$. The ECDSA scheme works as follows:

• $\textsf{KeyGen}(1^{\lambda })\rightarrow (x,Q)$: set a random private key $x \leftarrow Z_q$ and compute the corresponding public key $Q=[x] \cdot P$.

• $\textsf{Sign}(x,m)\rightarrow (r,s)$: generate the signature (r, s) using private key x, message m, and hash function H with codomain of size $\lambda$ bits. That is:

  • Set a random nonce $k \leftarrow Z^{*}_q$ and compute $R \leftarrow [k] \cdot P = (r_x,r_y)$, then set $r \leftarrow r_x \mod q$.

  • Compute $s \leftarrow k^{-1}\cdot (H(m) + r \cdot x) \mod q$ and output (r, s).

• $\textsf{Verify}(m;(r,s)) \rightarrow b \in \{0, 1\}$: equals 1 if the signature is valid; 0 otherwise. That is:

  • Compute $R \leftarrow s^{-1} \cdot ([H(m)] \cdot P+[r] \cdot Q) = (r_x,r_y)$.

  • If $r = r_x \mod q$, output 1; otherwise output 0.

Due to the structure of elliptic curves, if (r, s) is a valid signature, then its complement (r, $- s$) is also a valid signature. Thus, this gives rise to the malleability problem of the ECDSA scheme. To overcome this problem, one can follow the low-s rule, where the low-s is the value between 0 and $\frac{q-1}{2}$. Therefore, we assume that the output of the signing procedure is always the lower s value.

2.3 Ideal Functionalities

We describe below the ideal $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$ functionality that our protocol realizes, as well as the ideal functionalities queried by our protocol, namely, an ideal zero-knowledge proof (ZKP) functionality $\mathcal {F}_{\scriptstyle \textsf{ZKP}}$ and an ideal committed non-interactive zero-knowledge functionality $\mathcal {F}_{\scriptstyle \mathsf {Commit\text {-}ZK}}$ which are similar to the ones used in [14], as well as an ideal Multiplicative-to-Additive (MtA) functionality $\mathcal {F}_{\scriptstyle \textsf{MtA}}$. In this content, we assume that each functionality provides a fresh session identifier (sid) for each invocation of it. This can be achieved by having the parties exchange random strings between each other, which will be further concatenated then hashed so as to produce the session identifiers.

$\boldsymbol{\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}}$ Functionality. The $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$ functionality is composed of a key generation phase and a signing phase. In the key generation phase, the key pair (x, Q) is generated, where x is stored internally, and Q is given to the parties. In the signing phase, the signature on the given message is constructed and given to $\mathcal {P}_1$. The functionality is introduced in Fig. 1.

Fig. 1.

2-party ECDSA functionality $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$

$\boldsymbol{\mathcal {F}_{\scriptstyle \textsf{ZKP}}}$ Functionality. The $\mathcal {F}_{\scriptstyle \textsf{ZKP}}$ functionality is depicted in Fig. 2. With this functionality, one party can prove the knowledge of a witness w for an element y, such that the pair (y, w) satisfies the relation $\mathcal {R}$. For our protocol, this relation is $\mathcal {R}\leftarrow \{(Q, x) \in \mathbb {G}\times Z_q \vert Q = [x] \cdot P \}$ for public parameters $\mathbb {G}$ and its generator P, which allows to prove knowledge of the discrete log of an elliptic curve point. The sigma protocol of Schnorr [22] can be used to instantiate this functionality, which can be made non-interactive using the Fiat-Shamir paradigm in the random-oracle model [11].

Fig. 2.

$\mathcal {F}_{\scriptstyle \textsf{ZKP}}$

ZKPs are expected to satisfy three key properties, completeness, soundness, and zero knowledge. Completeness means that given a witness w for a statement $x\in \mathcal {R}$, there is an efficient algorithm that provides a convincing proof, i.e. it ensures that if two parties follow the protocol, the verifier accepts the proof. Soundness means a malicious prover cannot construct a convincing proof for $x \not \in \mathcal {R}$, i.e. soundness prevents the verifier from accepting a false proof of the statement. Also, zero-knowledge means that proof does not reveal the used witness w, i.e. it states that proof does not leak any information except for the truth of the statement.

$\boldsymbol{\mathcal {F}_{\scriptstyle \mathsf {Commit\text {-}ZK}}}$ Functionality. The $\mathcal {F}_{\scriptstyle \mathsf {Commit\text {-}ZK}}$ functionality is depicted in Fig. 3. Through this functionality, a party will be able to commit to its Non-interactive ZKP (NIZKP) and open it afterwards. As mentioned in [14], this functionality can be realized in the random oracle model by having the parties hash their NIZKP concatenated with a randomness r, which will be both opened in the decommitment phase.

Fig. 3.

$\mathcal {F}_{\scriptstyle \mathsf {Commit\text {-}ZK}}$

$\boldsymbol{\mathcal {F}_{\scriptstyle \textsf{MtA}}}$ Functionality. The $\mathcal {F}_{\scriptstyle \textsf{MtA}}$ functionality is depicted in Fig. 4. This functionality takes as an input the two values $\alpha$ and $\beta$ coming from $\mathcal {P}_1$ and $\mathcal {P}_2$ respectively, and forwards to them respectively two random values a and b, subject to the relation $a + b = \alpha \cdot \beta \mod q$, i.e., it transforms a multiplicative sharing of a secret to an additive sharing. As stated earlier, one can instantiate MtA from many constructions, such as the Paillier encryption scheme [20] or El Gamal [10], Castagnos-Laguillaumie (CL) [4] or OT [21].

Fig. 4.

$\mathcal {F}_{\scriptstyle \textsf{MtA}}$

3 Protocol

Our two party ECDSA protocol is composed of two phases; one phase for a distributed key generation that runs once, at the end of which the parties will hold an additive sharing of the secret x as $x = x_1+x_2$, then the second phase is for signing, which consists of:

• Generating the nonce k, which will be multiplicatively shared between the parties as $k=k_1 \cdot k_2$.

• Querying the MtA functionality, so as to convert the product of $\mathcal {P}_1$’s secret key $x_1$ and $\mathcal {P}_2$’s nonce $k_2^{-1}$ to an additive sharing $a+b$, namely, $\mathcal {P}_1$ and $\mathcal {P}_2$ receive a and b respectively such that $a+b=x_1.k_2^{-1} \mod q$. After the query, $\mathcal {P}_1$ computes $Z \leftarrow [a] \cdot P$ and sends it to $\mathcal {P}_2$, who computes $(Z + [b] \cdot P)\cdot k_2$ and checks if it is equal to $Q_1$, so as to control the correctness of the MtA input against a malicious $\mathcal {P}_1$.

• Online signing, that starts by $\mathcal {P}_2$ generating locally its share of the signature after the MtA invocation, namely $s_2=k_2^{-1}(H(m)+r.x_2)+b \cdot r \mod q$, then sends it to $\mathcal {P}_1$ who will generate the signature by calculating locally $s=k_1^{-1}(s_2+a \cdot r) \mod q$ and verifying whether this signature is valid. Note that the nonce generation and the MtA invocation are message-independent, thus we can refer to these two steps as the offline signing.

The complete process is illustrated in Fig. 5. Also the graphical representation of the key distribution and signing phase are given in Fig. 6 and Fig. 7, respectively.

Fig. 5.

2-party ECDSA Protocol

Security of our protocol is simulation based, following the real/ideal paradigm [24]. The type of adversary we considered is a malicious one with static corruption. This implies that the adversary $\mathcal {A}$ can deviate from the protocol, but the party he corrupts (either $\mathcal {P}_1$ or $\mathcal {P}_2$) is set prior to the protocol execution.

Theorem 2

The protocol of Fig. 5 securely implements the functionality of Fig. 1 in the ($\mathcal {F}_{\scriptstyle \textsf{ZKP}}, \mathcal {F}_{\scriptstyle \mathsf {Commit\text {-}ZK}}, \mathcal {F}_{\scriptstyle \textsf{MtA}}$)-hybrid model in the presence of a malicious static adversary under the ideal/real definition of [24], assuming the Computational Diffie-Hellman problem is hard.

The proof of theorem 2 is given in Appendix B.

Fig. 6.

The 2-Party ECDSA Key Distribution Protocol

Fig. 7.

The 2-Party ECDSA Signing Protocol

3.1 Cost Analysis

We analyze below the theoretical complexity of our two party ECDSA protocol, and compare it with the one of [14, 25].

Theoretical Complexity - Key Distribution. The distributed key generation consists of generating keys and zero-knowledge proofs. The computation cost can be examined in terms of EC multiplications as this is the heaviest operation performed. For the keys, each party carries out 1M to produce its share of the public key. On the other hand, two zero-knowledge proofs of knowledge of discrete log need to be produced. Using the standard Schnorr proofs in non-interactive from, each party carries out 1M as a prover and 2M as a verifier. Thus the key distribution requires 8M in total. For the communication cost, each party needs to send its share of the public key and the corresponding NIZKP, and $\mathcal {P}_1$, needs to send as well a commitment to its share at the beginning of the protocol, which consists of an output of the hash function H being used (of size $\lambda$ bits). Assuming one EC point can be represented in $\lambda$ bits, and a NIZKP consists of two field elements and one EC point, the size of data communicated between the parties is $9 \cdot \lambda$. Note that the cost of our key distribution is the same as [25], which is a negligible cost compared to the one of Lindell [14], as the latter is dominated by the usage of homomorphic encryption.

Theoretical Complexity-Signing. The computation cost of the signing protocol can be examined in terms of EC multiplications and MtA invocations. That is, the first step of the offline phase is similar to the key generation, except that the nonce is multiplicatively shared, thus each party needs to perform an extra EC multiplication so as to obtain R. Also, the calculation needed to check $\mathcal {P}_1$’s input to MtA requires 3 EC multiplications. Thus, it results in a computation cost of 13M, and a communication cost of $10 \cdot \lambda$. To obtain the total cost of the offline phase, one needs to add these costs to the executing of 1 MtA. The cost of this depends on the instantiation used, which can yield different results. For instance, MtA can be instantiated from the Paillier encryption scheme, i.e., the building block upon which [14] is based. This would result in a protocol where homomorphic encryption is used in the offline phase, with an inferior performance to that of [14], however with an improved online phase performance than [14]

In fact, the online phase consists of performing operations over a field by both parties, and a verification phase of the signature, which requires from the verifier (in our case $\mathcal {P}_1$) to carry out 2M. Thus neglecting the cost of operations over a field, the computation cost of the online phase if 2M. As for the communication cost, $\mathcal {P}_2$ needs to send one field element to $\mathcal {P}_1$, thus $\lambda$ bits of data need to be communicated between the parties.

Table 1 compares these costs with the ones of [14, 25]. For [14], the cost of the homomorphic operations is dominated by exponentiations modulo $N^2$ by numbers from $Z_N$. We refer to these exponentiations as E. The value N refers to the public key of Paillier, which determines the size of a Paillier encryption, which is a number from $Z_{N^2}$. MtA refers to the cost of invoking an instantiation of the MtA functionality.

As one can notice, the computation and communication cost of our online phase is the same as [25], which outperforms the one of [14], for which the online phase requires performing an extra exponentiation, and sending an encryption of Paillier (N is typically of size 2048 bits) instead of a field element. However, our offline phase outperforms the one of [25], as in our case the computation and communication required are reduced respectively by 1M, and $2 \cdot \lambda$.

Table 1. Cost Analysis of Signing

3.2 Implementation

We implemented our protocol in C++, over the secp256k1 curve standardized by NIST, which is the one used by Bitcoin. The hash function we used is Sha256, and for the curve operation we used the Secp256k1¹ C library. The implementation can be found in https://github.com/YounesTal1/2ecdsa

We took runtimes with an Amazon instance of “t2.xlarge" (16 GiB of memory and 4 vCPU), running with “Ubuntu 18.04.6 LTS", this instance was located in “us-east-1" (Virginia). The runtimes we obtained are given in Table 2. Note that our implementation used a single thread, and that the runtimes reflect only the computation cost of our protocol. These runtimes were obtained by calculating the average time needed for a 1000 key generation, where each key was used to sign 100 messages. Note also that the MtA implemented is a dummy one (one party receives the multiplicative share of the other party, and produces the additive shares for both parties), hence Table 2 contains the term MtA, where one can plug in the time needed to execute the MtA of their choice to obtain the overall runtime of the offline signing. As can be observed, our protocol is efficient in terms of the computation cost, for both key generation and signing. That is, the key generation only requires 1.05 ms and the offline phase (excluding the MtA call) requires 1.26ms. The difference in runtimes is mainly due to the five extra EC multiplications, namely two extra EC multiplications that need to be performed for calculating R, as the nonce is shared multiplicatively, and three extra EC multiplications that need to be performed for checking the correctness of $\mathcal {P}_1$’s input to MtA. The online phase only requires 0.1ms, as this is dominated by two EC multiplications for the signature verification.

Table 2. Runtimes in milliseconds of our protocol. These runtimes correspond to the time needed for one key generation, one execution of the offline phase, and one execution of the online phase.

To understand the impact of the MtA functionality on the runtimes, so as to give a comprehensive evaluation of our protocol, let us consider two cases, an OT based MtA, and a CL based MtA. For this we will base our analysis on the runtimes of [25]. That is, [25] implemented their protocol with different MtA instanciations. For the case of OT, the offline phase took 2.6ms and required 90.9 KBytes of data to be communicated (Table 4 of [25]). For the case of CL, the offline phase took 1386ms and required 1.7KB of data to be communicated (Table 5 of [25]). As for the online phase, it took 0.2ms, which is dominated by 2M operations.

As the offline phase of [25] consists of 14M+1MtA, and requires $12 \cdot \lambda$ +1MtA (see Table 1), for the case of OT, one would estimate the MtA runtime to be around 1.2ms, and the communication cost of the MtA to be 90.52 KBytes, thus based on this, our offline phase would take around 2.46ms and require 9.84 KBytes, hence a gain of 5.4% on the running time. For the case of CL, one would estimate the MtA runtime to be around 1384.6ms, and the communication cost of the MtA to be 1.32 KBytes, thus based on this, our offline phase would take around 1385.9ms and require 1.636 KBytes, hence a gain of 3.7% of the size of communicated data.

4 Conclusion

We proposed an efficient two-party ECDSA protocol secure against malicious adversaries. Our protocol has a light online phase, dominated by the verification step of ECDSA, and requires only sending one field element from one party to the other. Our offline phase uses a single call of the MtA functionality, and to the best of our knowledge, it offers the most efficient offline phase in terms of the computational and communication cost for such an online phase.

It is worth noting that the asymmetry introduced to the protocol, between what the two parties do, particularly the inputs they send to the MtA functionality, poses a challenge to generalize the protocol to the multiparty case with a low number of invocation to the MtA functionality (say at most equal to the number of parties). We leave further exploration as future work.

Appendices

A Proof of Theorem 1

The proof below is taken from [19].

Let us assume we can solve the Diffie-Hellman problem, then given the tuple (P,$[x]{\cdot } P)$ one can obtain $[x^{-1}] {\cdot } P = [x^{-1} {\cdot } x^{-1}] {\cdot } ([x] {\cdot } P)$ from solving the Diffie-Hellman problem over the tuple $([x]{\cdot }P$, $P=x^{-1}{\cdot }([x]{\cdot }P)$, $P=x^{-1}{\cdot }([x]{\cdot }P))$.

Conversely, let us assume we can solve the 1-Weak Diffie-Hellman problem, then given the tuple (P, $[a]{\cdot }P$, $[b]{\cdot }P)$, one can obtain $([a^2]{\cdot }P)$ from solving the 1-Weak Diffie-Hellman problem over the tuple $([a]{\cdot }P$, $P=a^{-1}{\cdot }([a]{\cdot } P))$. Similarly, one can obtain $([b^2] {\cdot } P)$ and $([(a+b)^2] {\cdot } P)$ from the tuples $([b]{\cdot }P$, P) and $([a + b] {\cdot }P$, P) respectively. Next, one can obtain ($[a {\cdot } b] {\cdot } P$) by calculating $2^{-1} {\cdot } [((a+b)^2 - (a)^2 - (b)^2)] {\cdot } P$.

B Proof of Theorem 2

In Fig. 8, we build a simulator $\mathcal {S}$, to simulate $\mathcal {P}_1$ when $\mathcal {P}_2$ is corrupt, and to simulate $\mathcal {P}_2$ when $\mathcal {P}_1$ is corrupt. Below, we sketch a proof to demonstrate why the views in a real and a simulated execution will be indistinguishable for an adversary $\mathcal {A}$.

Fig. 8.

2-party ECDSA Simulator

1.1 B.1 Corrupted $\mathcal {P}_1$

Key Generation Phase. The difference between the real execution and the simulated execution is the generation of $Q_2$. In the case of a real execution, $Q_2$ is computed as $[x_2] \cdot P$ where $x_2$ is randomly generated, while in the case of a simulated run, $Q_2$ is computed by calculating $Q_2 \leftarrow Q - Q_1$. Since Q is randomly generated by the $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$ functionality of Fig. 1 ($Q \leftarrow [x] \cdot P$ for a randomly generated x), then the distributions from which $Q_2$ is generated in the real and simulated executions are indistinguishable.

Signing Phase. In the nonce generation, a similar argument can be given to show that the views are indistinguishable. That is in a real execution, $R_2$ is computed as $[k_2] \cdot P$ where $k_2$ is randomly generated, while in the case of a simulated run, $R_2$ is computed by calculating $R_2 \leftarrow [k_1^{-1}] \cdot R$. Since R is randomly generated by $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$ ($R \leftarrow [k] \cdot P$ for a randomly generated k), then the distributions from which $R_2$ is generated in the real and simulated executions are indistinguishable.

In the MtA call, both in the real and simulated executions, $\mathcal {P}_1$ is intended to receive a randomly generated a, thus the views are indistinguishable. Afterwards, $\mathcal {P}_1$ sends Z to $\mathcal {P}_2$. In a simulated execution, $\mathcal {P}_2$ aborts if $\mathcal {P}_1$ has provided to the MtA functionality a different input than $x_1$, or if he sends a different value than $[a] \cdot P$. This behaviour is equivalent to what happens in a real execution, where $\mathcal {P}_2$ checks whether $k_2 \cdot (Z + [b] \cdot P) = Q_1$. That is, let us denote by $\epsilon _1$, the additive error that $\mathcal {P}_1$ can introduce to x, namely, $\mathcal {P}_1$ sends to MtA the value $x' \leftarrow x + \epsilon \mod q$, and by E, the additive error that $\mathcal {P}_1$ can introduce to Z, namely, $\mathcal {P}_1$ sends $\mathcal {P}_2$ the value $Z' \leftarrow Z + E$. To pass the check of $\mathcal {P}_2$, the following equation needs to be satisfied:

$$\begin{aligned} Q_1 & = k_2 \cdot (Z' + [b] \cdot P) \\ & = k_2 \cdot (E + Z + [b] \cdot P) \\ & = k_2 \cdot (E + [a] \cdot P + [b] \cdot P) \\ & = k_2 \cdot (E + (x_1 + \epsilon _1) \cdot k_2^{-1} \cdot P ) \\ & = k_2 \cdot (E + x_1 \cdot k_2^{-1} \cdot P + \epsilon _1 \cdot k_2^{-1} \cdot P) \\ & = Q_1 + k_2 \cdot (E + \epsilon _1 \cdot k_2^{-1} \cdot P) \\ \end{aligned}$$

which implies that $k_2 \cdot E + \epsilon _1 \cdot P = 0$. If $E = \mathcal {O}$, then $\epsilon _1 = 0$ mod q. Also if $\epsilon _1 = 0$ mod q, then $E = \mathcal {O}$ as $k_2 \ne 0$ mod q. Thus $E = \mathcal {O}$ or $\epsilon _1 = 0$ mod q implies that the adversary has not cheated, as we end up with a case where he does not modify the values he is supposed to send.

Let us look at the case where $E \ne \mathcal {O}$ and $\epsilon _1 \ne 0$ mod q. The equation holds if the adversary chooses $\epsilon _1$ in such a way that $E = \epsilon _1 \cdot [k_2^{-1}]\cdot P = \mathcal {O}$. While $R_2 = [k_2]\cdot P$ is known to the adversary, obtaining $[k_2^{-1}]\cdot P$ from it would mean breaking the 1-Weak Diffie-Hellman problem, which as we have seen is equivalent to the Computational Diffie-Hellman problem which is believed to be hard.

Thus to summarize, the adversary will not be able to make the check pass if he cheats, either in the MtA call or the step afterward.

In the online signing:

If the parties reach this stage, $\mathcal {P}_1$ will be receiving in the simulated execution $s_2 = s \cdot k_1 - a \cdot r \mod q$, which is equal to

$$\begin{aligned} s_2 & = s \cdot k_1 - a \cdot r \\ & = k^{-1} \cdot (H(m) + r \cdot x) \cdot k_1 - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x) - a \cdot r) \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_1 + r \cdot x_2) - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_2 ) + k_2^{-1} \cdot r \cdot x_1 - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_2 ) + r \cdot (a + b) - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_2 ) + r \cdot b \\ \end{aligned}$$

which is what $\mathcal {P}_1$ receives in a real execution.

1.2 B.2 Corrupted $\mathcal {P}_2$

Key Generation Phase. Similarly to the case of a corrupted $\mathcal {P}_1$, the difference between the real execution and the simulated execution is the generation of $Q_1$. In the case of a real execution, $Q_1$ is computed as $[x_1] \cdot P$ where $x_1$ is randomly generated, while in the case of a simulated run, $Q_1$ is computed by calculating $Q_1 \leftarrow Q - Q_2$. Since Q is randomly generated by the $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$ functionality of Fig. 1 ($Q \leftarrow [x] \cdot P$ for a randomly generated x), then the distributions from which $Q_1$ is generated in the real and simulated executions are indistinguishable.

Signing Phase. Similarly to the case of a corrupted $\mathcal {P}_1$, in the nonce generation, a similar argument can be given to show that the views are indistinguishable. That is in a real execution, $R_1$ is computed as $[k_1] \cdot P$ where $k_1$ is randomly generated, while in the case of a simulated run, $R_1$ is computed by calculating $R_1 \leftarrow [k_2^{-1}] \cdot R$. Since R is randomly generated by $\mathcal {F}_{\scriptstyle \textsf{2ECDSA}}$ ($R \leftarrow [k] \cdot P$ for a randomly generated k), then the distributions from which $R_1$ is generated in the real and simulated executions are indistinguishable.

In the MtA call, both in a real and simulated executions, $\mathcal {P}_2$ is intended to receive a randomly generated b (In the simulated execution $b = x_1 \cdot k_2^{-1} - a \mod q$ for a randomly generated a. Note that the Simulator uses here and in what follows the $k_2$ he received at the MtA call, and not the one received during the nonce generation), thus the views are indistinguishable. In the step afterwards, in the simulated execution, $\mathcal {P}_2$ receives $[k^{-1}_2] \cdot Q_1 - [b] \cdot P$, which is the same as what he receives in a real execution, as $[k^{-1}_2] \cdot Q_1 - [b] \cdot P = [k^{-1}_2 \cdot x_1] \cdot P - [b] \cdot P = [a] \cdot P$. Thus the views are indistinguishable.

In the online signing:

• if $\mathcal {P}_2$ does not cheat at all during the protocol, he will be able to calculate $s_2 = k_2^{-1} \cdot (H(m) + x_2 \cdot r) + b \cdot r \mod q$ and send it to $\mathcal {P}_1$. In the real execution $\mathcal {P}_1$ will add it to its share $s_1$, and the sum will yield a valid signature which will be published by $\mathcal {P}_1$. In the simulated execution, $s_2$ will pass the check of the simulator and therefore he will publish the signature.

• if $\mathcal {P}_2$ cheated at the MtA call, or does not send the correct $s_2$, in the real execution, $\mathcal {P}_1$ will not find a valid signature after summing up its share with the one of $\mathcal {P}_2$, thus $\mathcal {P}_1$ will send the abort signal. In the simulated execution, either $\textsf{cheat}$ flag will be equal to 1 at this stage, or $s_2$ will not pass the check of the simulator. In both cases the simulator will abort. That is, the only case where the views will be distinguishable, is when the adversary cheats on the MtA call, and yet manages to send the correct $s_2$. Let us denote by $\epsilon$, the additive error that the adversary introduces to his input to MtA, namely he sends $k_2^{-1} + \epsilon$ instead of $k_2^{-1}$. In this case $a+b = x_1 \cdot (k_2^{-1} + \epsilon )$. In order to pass the check, $\mathcal {P}_2$ needs to send $s_2$ such that $s \cdot k_1 = s_2 + a \cdot r \mod q$. This implies that:

  $$\begin{aligned} s_2 & = s \cdot k_1 - a \cdot r \\ & = k^{-1} \cdot (H(m) + r \cdot x) \cdot k_1 - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_1 + r \cdot x_2) - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_2 ) + k_2^{-1} \cdot r \cdot x_1 - a \cdot r \\ & = k_2^{-1} \cdot (H(m) + r \cdot x_2 ) + r \cdot b - x_1 \cdot r \cdot \epsilon \\ \end{aligned}$$

  As $x_1$ is unknown to the adversary, he can satisfy this equation only if $\epsilon = 0$, i.e., the case where he does not cheat in the MtA call. Thus the behaviour of the simulator will make the real execution and the simulated one indistinguishable.