Fast threshold ECDSA with honest majority 1

Abstract

ECDSA is a widely adopted digital signature standard. A number of threshold protocols for ECDSA have been developed that let a set of parties jointly generate the secret signing key and compute signatures, without ever revealing the signing key. Threshold protocols for ECDSA have seen recent interest, in particular due to the need for additional security in cryptocurrency wallets where leakage of the signing key is equivalent to an immediate loss of money.

We propose a threshold ECDSA protocol secure against an active adversary in the honest majority model with abort. Our protocol is efficient in terms of both computation and bandwidth usage, and it allows the parties to pre-process parts of the signature, such that once the message to sign becomes known, they can compute a secret sharing of the signature very efficiently, using only local operations. We also show how to obtain guaranteed output delivery (and hence also fairness) in the online phase at the cost of some additional pre-processing work, i.e., such that it either aborts during the pre-processing phase, in which case nothing is revealed, or the signature is guaranteed to be delivered to all honest parties online.

Keywords

Cryptographic protocols threshold cryptography ECDSA

1. Introduction

A hot topic of the 80s was threshold cryptography [15,16]. This notion covers encryption and signature schemes where the key is secret shared among a number of parties in a way that lets the parties sign or decrypt messages despite the fact that the key remains secret shared. The key remains protected as long as at most a certain threshold t of the parties are corrupted.

Threshold cryptography, being a special kind of secure multiparty computation, is stronger than simply secret sharing the key, since it allows to sign or encrypt without any one party reconstructing the key. Threshold cryptography therefore increases security by ensuring that an attacker must compromise $t + 1$ points instead of a single point. It is also well-suited in cases with multiple owners of the key and where it should be enforced that signing or decryption only occur when a certain threshold of the owners agree.

The elliptic curve digital signature standard ECDSA [27,30] has recently become very popular. It has for example been adopted by TLS, DNSSec, and popular cryptocurrencies such as Bitcoin and Ethereum. This has caused a growing need for a threshold version of ECDSA. In particular, its use in cryptocurrencies implies that loss of the secret signing key immediately translates to a loss of money.2

²
For this reason Bitcoin uses multisignatures [1]. But as discussed in length in e.g. Gennaro et al. [21] threshold signatures are in several ways more suited.

However, while efficient threshold versions of e.g. RSA, ElGamal encryption, and Schnorr signatures have been proposed early [38,40], efficient threshold variants of DSA/ECDSA have proved harder to achieve, mainly due to the fact that this involves both computing $g^{k}$ and multiplication of the secret key x with the inverse of k (in $Z_{q}$ ), where both x and k must remain secret shared.

1.1. Previous related work

Threshold DSA/ECDSA signatures can of course be computed using general MPC [3,11,26,42], but until recently this has been regarded as too inefficient.

In 1996 Gennaro et al.proposed a specialized threshold protocols for DSA signatures in the model with honest majority [22–24].

MacKenzie and Reiter later proposed the first DSA/ECDSA threshold scheme for two parties [33]. From 2016 and on, motivated by the application of threshold ECDSA in cryptocurrencies, there have been many results [4,9,10,17,18,20,21,31,32], all in the dishonest majority setting. The first of these were not really practical, especially due to a heavy key generation procedure. But the most recent are quite practical and works for any threshold $t < n$ [10,18,20,32]. Put shortly, they handle the multiplication of secrets either by using additively homomorphic schemes such as Paillier encryption [34] or class group based cryptosystems, or Gilboa’s technique for MPC multiplication based on oblivious transfer [25] (which means that the protocol inherits the performance gain from the recent advances in OT-extension [5,29]), combined with clever tricks to avoid heavy zero-knowledge proofs.

1.2. Concurrent work

Non-interactive online signing. It turns out that threshold ECDSA is well-suited for the online/offline setting, since most of the work can be done before the message to sign is known (offline). The result of the offline phase is sometimes called a presignature. This can help spread out the overall work more evenly, e.g., by computing presignatures offline a higher signature throughput can be obtained during peak hours (online).

In some cases, the online phase can even be non-interactive. This means that when both a presignature and the message are available, the parties can locally compute shares of the signature, which they can then send to the intended receiver of the signature. Non-interactive online signing is useful in practice because the signature receiver can just collect the shares from the servers one at a time. The servers need not be online at the same time. In addition, it is common in the context of cryptocurrencies to increase security by keeping the key shares (and presignatures) in “cold” storage, i.e., on external media that is not directly accessible from the network, e.g. on a USB stick or even in a bank box. With non-interactive online signing only a single round-trip to the cold storage is required to produce a signature.

Recent concurrent work of Canetti et al. [8] adapts existing protocols in the dishonest majority setting [20] to achieve non-interactive online signing along with other properties such as proactive security.

Threshold signatures with large numbers of parties. Recently, a use case has been proposed by the Keep Network3

³
http://keep.network

for interoperability between different cryptocurrencies. This solution requires large amounts of cryptocurrency being held by a central party. To maintain the distributed nature of exisitng blockchains, it has been proposed to replace this trusted party with a threshold signing protocol. This means that the number of parties in the signing protocol must be large, e.g., not just a few parties, but perhaps 500 or 1000.

As discovered by Keep network, this leads to a problem when using the recent ECDSA solutions for dishonest majority [10,18,20,32]. These protocols all have the property that a single malicious party taking part in the signing may cause the protocol to abort, without being identified as the malicious party. Suppose that there are, e.g., 500 parties and 400 are required to sign. With no identifiable abort it can be hard to pick a subset of 400 honest parties even if only a small fraction of the parties are malicious, and so the signing will in effect be blocked. With identifiable abort the malicioius parties can be excluded from further signing attempts.

This insight has motivated recent concurrent work on threshold ECDSA with identifiable abort [8,19]. Canettie et al. [8] extend earlier results [20] to obtain both identifiable abort and non-interactive online signing. Gagol et al. [19] adapts the protocol of Lindell & Nof [32]. They require multiple rounds of communication online and participation of all parties in the offline phase, but on the other hand they achieve not only identifiable abort in the online phase, but also the property that the online signing has guaranteed output delivery if more than $n / 2$ honest parties participate in the signing. I.e., online signing succeeds even if a few malicious parties participate. This notion of guaranteed output delivery makes signing with a large number of parties much more practical.

Signing with general MPC. Recent results [14,39] show how to do threshold ECDSA efficiently, based on schemes for general MPC over a large field. This of course involves the full machinery of general MPC, but it also gives flexibility since one can achive different trade-offs between performance and security by choosing differnt schemes for general MPC. In particular, as shown by Dalskov et al. [14], when plugging into their solution the currently fastest protocol for general MPC in the honest majority model with abort [12], this leads to a practical protocol with performance similar to ours (only a few heavy curve multiplications per party, leading to a throughput of thousands of signatures per second).

1.3. Our contribution

We provide a practical and efficient threshold protocol for DSA and ECDSA signatures in the honest majority model with abort. It is secure against an active adversary and works for any number of parties n and security thresholds t as long as $n ⩾ 2 t + 1$ . For $n = 3$ , each party only needs to do five long exponentiations.

The protocol is accompanied by a full proof in the UC model [7]. The proof shows that our protocol (perfectly) realizes the standard ECDSA functionality, and it relies on no additional assumptions.

The protocol is well-suited for the online/offline model: Most of the work can be done in an offline phase before the message to be signed is known. Doing so, the protocol achieves excellent online performance. In particular, when the parties receive the message to be signed, they can compute a sharing of the signature non-interactively, using only local operations.4

⁴
Note that threshold ECDSA with a non-interactive online phase is only possible under a slightly stronger assumption than the standandard ECDSA assumption, where the adversary sees $g^{k}$ before his attempt to forge a signature. It was proved by Canetti et al. [8] that this enhanced ECDSA assumption is equivalent to regular ECDSA in the generic group model and that this also holds in some cases in the random oracle model.

We show how to extend our basic protocol with a little more work in the offline phase in order to achieve a non-interactive online phase with guaranteed output delivery.

We demonstrate practicality by benchmarking in the LAN as well as the WAN setting. Using a close-to-real-world deployment with load balancers and authenticated channels we show that our protocol achieves both low latency and high throughput.

Our protocol compared to existing dishonest majority protocols. The ECDSA protocols for dishonest majority [4,9,10,17,17,18,20,21,31–33] all rely on computationally heavy primitives such as Paillier encryption and zero-knowledge proofs, or they are based on oblivious transfer [17,18] which incurs high bandwith. In comparison, our protocol is considerably simpler and efficient in terms of both computation and bandwidth usage, leading to a higher overall signature throughput.

In addition, except from Doerner et al. [18], these protocols somehow relax security, either by relying on assumptions not implied by ECDSA itself, such as decisional Diffie-Hellman [32] or the quadratic residuosity assumption [20,31], or they implement relaxed versions of the ECDSA functionality [17]. In contrast, for our basic protocol we provide a proof in the UC model that our protocol (perfectly) implements the standard ECDSA functionality without additional assumptions.

That said, all of these protocols of course achieve stronger security in the sense that they can tolerate up to $n - 1$ corruptions.

Our protocol compared to the GJKR protocol [ 22 – 24 ]. The protocol of Gennaro et al. [22–24] achieves full security in the honest majority model, i.e., including fairness and guaranteed output delivery. Their protocol assumes a consistent and reliable broadcast channel and uses Pedersen’s verifiable secret sharing [35]. Correctness of the multiplication of secret sharings is ensured using error correcing codes, and the authors give a simulation-based proof of security against a static, malicious adversary corrupting at most t out of n parties for $n ⩾ 4 t + 1$ .

Gennaro et al. [24] also sketches a variant of their protocol that works for $n ⩾ 3 t + 1$ . Instead of error correcting codes, this protocol ensures correctness of the multiplication using a clever trick to produce a verifiable sharing of the product, utilizing the fact that one of the factors in the product is produced by adding several random sharings produced by Pedersen’s VSS. None of these protocols work for the optimal threshold $n = 2 t + 1$ .

We present a simple and efficient protocol that is built specifically for the $n ⩾ 2 t + 1$ model with abort and we include a full proof in the UC model [7].

While not directly mentioned in Gennaro et al. [24], their variant for $n ⩾ 3 t + 1$ could be adapted to work in the setting with $n ⩾ 2 t + 1$ and abort. However, the result would be more complex and require substantially more computation compared to our solution.

In particular, we avoid using Pedersen VSS and we use a new trick for verification of the multiplication that is simpler and more efficient. (It leaks one of the factors in the exponent, but this is fine in our context of ECDSA as $g^{k}$ is to be revealed anyway.)

As a result our protocol allows non-interactive online signing, and requires only two long exponentiations online. For $n = 3, t = 1$ our protocol involves roughly 13% of the computation require by the variant of GJKR that can run in the $n ⩾ 2 t + 1$ setting with abort.

In addition, we show how to extend our protocol with additional work in the pre-processing phase, such that once it succeeds, we get guaranteed output delivery in the online phase, in the sense that any $t + 1$ honest parties will be able to produce signatures. The protocols in Gennaro et al. [24] require at least $2 t + 1$ honest parties online.

2. Basic tools and definitions

2.1. Signature schemes

Recall that a signature scheme is defined by three efficient algorithms: $p k, s k \leftarrow Gen (1^{κ})$ ; $σ \leftarrow {Sign}_{s k} (M)$ ; $b \leftarrow {Verify}_{p k} (M, σ)$ [28]. A signature scheme satisfies two properties:

Correctness. With overwhelmingly high probability (in the security parameter κ) it must hold that all valid signatures must verify.

Existential unforgeability. This is modeled with the following game $G_{FORGE}$ :

Run $p k, s k \leftarrow Gen (1^{κ})$ ; input $p k$ to the adversary A.

On $(SIGN, M)$ from A:

Return $σ \leftarrow {Sign}_{s k} (M)$ to A and add M to a set Q.

On $(FORGE, M^{'}, σ^{'})$ from A:

If $M^{'} \notin Q$ and ${Verify}_{p k} (M^{'}, σ^{'}) = ⊤$ , output ⊤ and halt; else output ⊥ and halt.

The signature scheme is existentially unforgeable if for any PPT A the probability

Pr [G_{FORGE} = ⊤]

is negligible in κ. That is, even with access to a signing oracle, no adversary can produce a valid signature.

A correct and existentially unforgeable signature scheme is simply called secure.

2.2. The DSA/ECDSA standard

An instance of the DSA signature scheme [27,30] has the parameters $\begin{array}{l} (G, q, g, H, F) \leftarrow Gen (1^{κ}) \end{array}$ where G is a cyclic group of order q with generator $g \in G$ , H a hash function $H : {0, 1}^{*} \mapsto Z_{q}$ and F a function $F : G \mapsto Z_{q}$ .

For $a, b \in G$ we will let $a b$ denote the group operation (multiplicative notation). For $c \in Z_{q}$ and $g \in G$ we let $g^{c}$ denote $g g \dots g$ , i.e., the group operation applied c times on g.

A key pair is generated by sampling uniformly the private key $x \in Z_{q}$ and computing the public key as $y = g^{x}$ . Given a message $M \in {0, 1}^{*}$ a signature is computed as follows: Let $m = H (M)$ . Pick a random $k \in Z_{q}$ , set $R = g^{k}$ , $r = F (R)$ , $s = k^{- 1} (m + r x)$ . The resulting signature is $r, s$ . Given a public key y, a message M and signature $r, s$ , one can verify the signature by computing $m = H (M)$ and checking that $r = F (g^{m s^{- 1}} y^{r s^{- 1}})$ .

In DSA G is $Z_{p}$ for some prime $p > q$ . In ECDSA G is generated by a point g on an elliptic curve over $Z_{p}$ for some $p > q$ . In this case $F : G \mapsto Z_{q}$ is the function that given $R = (R_{x}, R_{y}) \in G \subset Z_{p} \times Z_{p}$ outputs $R_{x} mod q$ .

ECDSA has been proved secure in the Generic Group Model assuming that computing the discrete log in G is hard, and assuming that H is collision resistant and uniform [6].

Our protocol works for both DSA and ECDSA. In particular, it is suitable for ECDSA with the “Bitcoin” curve secp256k1 that is believed to have a 128-bit security level.

2.3. Shamir’s secret sharing

Recall that in Shamir’s secret sharing scheme [37] a dealer can secret share a value $m \in Z_{q}$ (for a prime number q) among n parties by choosing a random degree t polynomial $f (x)$ over $Z_{q}$ subject to $f (0) = m$ . The dealer then sends a share $m_{i} = f (i)$ to each party $P_{i}$ . This reveals no information about m as long as at most t parties are corrupted. We will use $[m]$ to denote such a sharing where each party $P_{i}$ holds a share $m_{i}$ .

If the dealer is honest, any subset of $t + 1$ parties can reconstruct the secret using Lagrange interpolation. More generally, one can compute the value $f (j)$ for any value $j \in Z_{q}$ on a degree t polynomial $f ()$ using Lagrange interpolation given values $y_{i} = f (x_{i})$ for any $t + 1$ distinct values $x_{i}$ . For the specific values $f (1), f (2), \dots, f (t + 1)$ we can efficiently compute $f (j)$ for any $j \in Z_{q}$ as $\begin{array}{l} f (j) = λ_{1} (j) f (1) + λ_{2} (j) f (2) + \dots + λ_{t + 1} (j) f (t + 1) \end{array}$ where the Lagrange coefficients are defined as $\begin{array}{l} λ_{i} (j) : = \prod_{1 < l < t + 1, l \neq i} \frac{j - l}{i - l} . \end{array}$ For example, for $n = 3$ , $t = 1$ and $j = 3$ we have $λ_{1} = (3 - 2) / (1 - 2) = - 1$ and $λ_{2} = (3 - 1) / (2 - 1) = 2$ so for any degree-1 polynomial $f (x) = a x + b$ we can compute $f (3) = - 1 \cdot f (1) + 2 \cdot f (2)$ .

For $g \in G$ we will sometimes do Lagrange interpolation in “the exponent” as follows: For $Y_{1} = g^{f (1)}, Y_{2} = g^{f (2)}, \dots, Y_{t + 1} = g^{f (t + 1)}$ define $\begin{array}{l} ExpInt (Y_{1}, Y_{2}, \dots Y_{t + 1}; j) : = \prod_{i = 1}^{t + 1} Y_{i}^{λ_{i} (j)} = g^{\sum_{i = 1}^{t + 1} λ_{i} (j) \cdot y_{i}} = g^{f (j)} . \end{array}$

We will also need to interpolate the value $p (0)$ on a degree $2 t$ polynomial $p (x)$ from the $2 t + 1$ values $p (1), p (2), \dots, p (2 t + 1)$ . We denote this function $\begin{array}{l} Int2t (p (1), p (2), \dots, p (2 t + 1)) . \end{array}$

Recall that Shamir’s secret sharing scheme is linear. This means that once sharings $[m_{1}]$ and $[m_{2}]$ are established, and if the parties agree on a public constant $a \in Z_{q}$ then they can compute $[a \cdot m_{1}]$ and $[m_{1} + m_{2}]$ efficiently, without communicating. We use $a \cdot [m_{1}]$ and $[m_{1}] + [m_{2}]$ to denote these operations.

2.4. Joint random secret sharing

We will need a protocol $[r] \leftarrow RSS (t)$ to generate a Shamir sharing of a random value r over a random degree-t polynomial $f_{r}$ such that no party learns the value r. For this we use the common technique where each party $P_{i}$ acts as dealer for a random degree t polynomial $f^{(i)}$ of his choice. Using that secret sharing is linear, each party can then compute its share $r_{i}$ of $[r]$ as $r_{i}^{(1)} + r_{i}^{(2)} + \dots + r_{i}^{(n)}$ .

If one or more parties are malicious, the resulting sharing $[r]$ may be inconsistent, meaning that the shares held by the honest parties are not points on any degree t polynomial. But in this case, the shares held by the honest parties are still uniformly random, since at least some of the values $r^{(j)}$ are random.

Similarly, a random Shamir sharing of zero can be created if each party $P_{i}$ chooses $f^{(i)}$ at random, but subject to $f^{(i)} (0) = 0$ . We denote this by $[0] \leftarrow ZSS (t)$ . In this case, however, if there is a malicious party, it is not guaranteed that the sharing is in fact a sharing of zero.

3. Our threshold ECDSA protocol

In this section we describe our basic protocol and the overall strategy for its simulation. To keep the description simple, we focus on the basic protocol and consider pre-processing and guaranteed output delivery later.

3.1. Technical overview

At a high level, we follow the scheme of Gennaro et al. [24]. The parties first generate the private key $[x]$ using joint random secret sharing. Then they run a protocol to reveal the public key $y = g^{x}$ . To avoid certain subtleties related to joint random secret sharing with guaranteed termination [23], and to avoid additional assumptions, Gennaro et al.use a rather complicated protocol based on Pedersen verifiable secret sharing. Since we allow abort, we can use plain Shamir secret sharing along with a simpler protocol for revealing $g^{x}$ . Our protocol for revealing $g^{x}$ works despite malicious parties and is designed to abort also if $[x]$ is not a consistent sharing.

When signing a message M, the parties generate a sharing of the nonce $[k]$ using joint random secret sharing and reveal $g^{k}$ using the same protocol as for revealing the public key $g^{x}$ . They then use Beaver’s inversion trick to compute $[k^{- 1}]$ : They first generate a random sharing $[a]$ , then multiply and open $w = [a] [k]$ . This is done using a simple passively secure protocol where the parties just reveal the product of their shares. Since this is a degree $2 t$ sharing of $a k$ they can recover $a k$ as long as all parties participate honestly. With malicious parties the result is not necessarily correct. Gennaro et al.used error correcting codes to handle this. We tolerate abort and can instead use the same protocol as before to correctly open an authenticator $W = g^{a k}$ that lets the parties verify the correctness by checking that $g^{w} = W$ .

If ok, the parties compute $[a] \cdot w^{- 1} = [k^{- 1}]$ and $m = H (M)$ , and they can now compute and open $[s] = [k^{- 1}] (m + r [x])$ as they opened $[a] [k]$ before. This time, however, since we tolerate abort, it suffices to check correctness of s by validating the resulting signature $(r, s)$ on M using the public key y.

3.2. Computing powers of a point

A central building block in our protocol is a subprotocol that given a sharing $[x]$ and a generator $g \in G$ (on which all honest parties agree) reveals the value $y = g^{x}$ . We let $y \leftarrow POWOPEN (g, [x])$ denote this protocol.

The protocol works as follows:

Each party $P_{i}$ sends $y_{i} = g^{x_{i}}$ to all the other parties. Let f be the unique degree t polynomial defined by the $t + 1$ (or more) honest parties’ shares, i.e. $f (0) = x$ .

When $P_{i}$ receives all $g^{x_{j}}$ for each $y_{j} \in {y_{t + 2}, y_{t + 3}, \dots, y_{n}}$ it verifies that $y_{j}$ is consistent with the degree t polynomial defined by the first $t + 1$ values $y_{1}, y_{2}, \dots, y_{t + 1}$ . It does so by doing Lagrange interpolation “in the exponent”.

If so, $P_{i}$ knows that $y_{1}, \dots, y_{t + 1}$ are valid points on f, and $P_{i}$ then uses again Lagrange interpolation “in the exponent” on $y_{1}, y_{2}, \dots, y_{t + 1}$ to compute $y = g^{x} = g^{f (0)}$ .

Since $n ⩾ 2 t + 1$ there are at least $t + 1$ honest parties. This means that each honest party will receive at least $t + 1$ correct shares “in the exponent”, enough to uniquely define f. Hence, if any of the t corrupted parties cheat, all honest parties will abort in Step 2.

Intuitively, seeing the values $g^{x_{i}}$ reveals nothing on the shares $x_{i}$ since computing discrete logarithms in G is assumed to be hard. As we will later see, our simulation does in fact not rely on this property. The simulation works even for computationally unbounded adversaries.

A notable feature of $POWOPEN$ is that for $n ⩾ 2 t + 1$ all honest parties will abort if the input sharing defined by the honest parties is inconsistent, i.e., if these shares are not points on a degree t polynomial, no matter what the corrupted parties do.

Simulation. Consider how to simulate $POWOPEN$ . The simulator does not know the value x and so must use random shares $x_{j}$ for the corrupted parties. During simulation each party $P_{i}$ reveals $g^{x_{i}}$ to all other parties. The challenge is that the simulator only knows t points on the polynomial f, namely $f (j)$ for the corrupted parties $P_{j}$ . (This follows from the context in which $POWOPEN$ is used, see e.g. next section on key generation.) But the simulated adversary sees all $y_{i} = g^{x_{i}}$ . So in order to succeed, the simulator must make these values consistent with the environment’s view (which includes $y = g^{x}$ ). In other words, the simulator must use values $y_{i}^{'}$ such that $ExpInt (y_{i}^{'}; 0) = y = g^{x}$ , but without knowing x.

Simulation is possible since the simulator knows an additional point on f “in the exponent”, namely $y = g^{x} = g^{f (0)}$ (this requires that y is leaked to the adversary/simulator at the beginning of the protocol). So “in the exponent” the simulator knows $t + 1$ points on f, enough to fully determine f. Thus, using Lagrange interpolation “in the exponent” with y and the t random shares of the corrupted parties, the simulator can compute points to use for the honest parties in the simulation that are consistent with the adversary’s view that includes $y = g^{x}$ .

3.3. Key generation

The aim of key generation is to have the parties generate a sharing $[x]$ of a uniformly random value $x \in Z_{q}$ and reveal to each party $y = g^{x}$ . To generate $[x]$ the parties run $[x] \leftarrow RSS (t)$ to obtain a sharing of a random value $x \in Z_{q}$ over a random polynomial. To obtain $y = g^{x}$ we let the parties run the protocol $y \leftarrow POWOPEN (g, [x])$ .

Regarding correctness: We use plain Shamir sharing and not verifiable secret sharing (VSS). This means that a single malicious party $P_{i}$ may cause $[x]$ to be an inconsistent sharing, by dealing inconsistently for $x^{(i)}$ . As discussed above, this will cause $POWOPEN$ to abort, which is enough in our case, as we allow abort. Also, at least one party $P_{j}$ will correctly choose uniform shares $x_{j}^{(i)}$ , which is enough to ensure that $[x]$ is random and that all honest parties’ shares of x are random.

An important part of the protocol is that no honest party $P_{i}$ reveals his value $g^{x_{i}}$ until he has received shares $x_{j}$ from all other parties $P_{j}$ . This forces the corrupt parties $P_{j}$ to “commit” to their values $x^{(j)}$ before they see y. Without this, a corrupt party $P_{j}$ could let $x^{(j)}$ depend on y.

The protocol guarantees that if two parties output a public key, they output the same public key y. In addition, all subsets of $t + 1$ honest parties that receive output, will receive shares of the same private key x satisfying $g^{x} = y$ . The protocol also ensures that each share $x_{i}$ and the private key x (and hence also the public key) is uniformly distributed.

By having all parties send an ACK message to the others once they have succeeded, and require that parties only continue once an ACK have been received from all other parties, we get the property that the adversary can decide to abort or not, but if an honest party delivers output then so do all honest parties.

Regarding simulation, $RSS$ is information-theoretically secure so the simulator can just simulate the protocol using random values $x_{i}^{'}$ , and we already described how to simulate $POWOPEN$ .

3.4. Signature generation

Assume that key generation has been done without abort, such that the parties hold a consistent sharing of a random key $[x]$ and each party holds the corresponding public key $y = g^{x}$ . Assume also that the parties agree on the (hashed) message $m \in Z_{q}$ to be signed. Then the signature protocol proceeds as follows.

First a random sharing $[k]$ is generated and $R = g^{k}$ is revealed, using the $RSS$ and $POWOPEN$ protocols. We then compute $[k^{- 1}]$ using Beaver’s inversion protocol. The idea is to compute a random $[a]$ and open $[a] [k]$ (a is used to blind k). Then $[k^{- 1}]$ can be computed locally as $[a] \cdot w^{- 1}$ .

So we let the parties generate $[a]$ using $RSS$ and then compute $[w] = [a] [k]$ and open $[w]$ . The multiplication is done as follows: The parties simply compute their shares $w_{i} = a_{i} k_{i}$ . This results in shares on a polynomial $f_{w}$ of degree $2 t$ with $f_{w} (0) = w$ . But since $n ⩾ 2 t + 1$ there are enough parties $(2 t + 1)$ to interpolate w if they all reveal their shares. To avoid that their shares leak unintended information, they first compute a random degree $2 t$ zero sharing $[b] \leftarrow ZSS (2 t)$ and then reveal instead shares $a_{i} k_{i} + b_{i}$ . We denote this protocol $w \leftarrow WMULOPEN ([a], [k]; [b])$ . The “w” is for “weak”, since a single malicious party can cause the protocol to output anything. The only guarantee provided by the protocol is that it reveals no information about a and k, except of course the product $a k$ .

Recall that $[a]$ and $[b]$ , being generated using $RSS$ and $ZSS$ , are not known to be consistent sharings at this point. But at least each share $b_{i}$ is known to be a random value that blinds the share $a_{i} k_{i}$ , which is not necessarily random.

Note that there is not enough shares for any error detection on w: A single corrupt party could reveal a bad share $w_{i}$ resulting in the parties ending up with a wrong value of w. To deal with this we use a trick in order to compute an authenticator $W = g^{a k}$ . This allows each party to check that $g^{w} = W$ and abort if not. W is computed as follows: Recall that $g^{k}$ was correctly computed by $POWOPEN$ . The parties then invoke $POWOPEN$ again, this time using $g^{k}$ as the base, i.e. they compute $g^{a k} \leftarrow POWOPEN (g^{k}, [a])$ . Since correctness of $POWOPEN$ is ensured as explained above, even if $[a]$ is not a consistent sharing, all honest parties will abort at this point unless $w = a k$ .

Finally, given $[x]$ , $[k^{- 1}]$ , $r = F (g^{k})$ and the message m to sign, the parties compute the value $\begin{array}{l} [s] = [k^{- 1}] (m + r [x]) . \end{array}$

Note that this boils down to another multiplication of two degree t sharings, which can be done locally since $n ⩾ 2 t + 1$ , resulting in a degree $2 t$ sharing, Again, to avoid that the shares leak information, a random degree $2 t$ zero sharing $[c]$ is created using $ZSS$ and each party reveals $s_{i} = h_{i} (m + r x_{i}) + c i$ where $h_{i}$ is party $P_{i}$ ’s share of $k^{- 1}$ .

As before when opening $a k$ , the resulting value s can be recovered from $2 t + 1$ shares, but when $n = 2 t + 1$ there is not enough shares to do any error detection. So a single party can introduce any error on s. Before, we detected this by computing correctly the authenticator $g^{a k}$ . This time we instead just lets the parties verify the resulting signature $(r, s)$ on the message m using the public key y. Our analysis below shows that the only way the adversary can make the protocol succeed is by not introducing any fault on s.

Coping with message disagreement. To obtain a practical protocol we must make sure that the protocol aborts and no information leaks even if the honest parties do not agree on the message m to sign. Suppose that honest party $P_{1}$ got message $m + Δ$ while the other honest parties used m. Then $P_{1}$ would reveal $s_{1} = h_{1} (m + Δ + r x_{1}) + c_{1}$ . Anyone receiving all shares could then compute $s^{'} = \sum λ_{i} (0) \cdot s_{i} = s + λ_{1} h_{1} Δ$ (where $λ_{i}$ are the Lagrange coefficients). This shows that if an adversary could introduce an error on the message used by an honest party and somehow obtain the correct signature s then that party’s share of k would have leaked.

To avoid this, the parties could of course send the message to each other and abort if there is any mismatch, and then proceed by opening s. But for efficiency, we would like a protocol that only requires one round once the message is known. To achieve this (assuming $n = 2 t + 1$ ), we do as follows: During the initial rounds, we generate not just one zero-sharing $[c]$ , but two degree $2 t$ sharings of zero, $[d]$ , $[e]$ , using $ZSS (2 t)$ . When signing we then compute $\begin{array}{l} [s] = [k^{- 1}] (m + r [x]) + [d] + m [e] . \end{array}$ If all parties are honest and agree on m then $[d] + m [e] = [0]$ . If not, then $[d] + m [e]$ turns into a random pad that completely hides the honest parties shares $s_{i}$ and ensures that the verification will fail. Note that $[d]$ and $[e]$ may not be zero, or may even be inconsistent, but it is guaranteed that each share of d and e are at least random, which is all that we need here. Generally, for $n = 2 t + τ$ , we can blind by adding the value $[d] + m [e_{1}] + m^{2} [e_{2}] + \dots + m^{τ} [e_{τ}]$ .

Simulation. The simulator uses the same simulation strategy when simulating $R \leftarrow POWOPEN (g, [k])$ as when simulating $y \leftarrow POWOPEN (g, [x])$ , i.e., where Lagrange interpolation “in the coefficient” allows to patch the honest parties’ values $g^{k_{i}}$ . The use of a uniformly random $[a]$ to blind $[k]$ means that the simulator can run $W \leftarrow POWOPEN (R, [a])$ and $w \leftarrow WMULOPEN ([a], [k]; [b])$ without patching. Finally, $s \leftarrow WMULOPEN ([k^{- 1}], [m + r x]; [c])$ can be simulated because the simulator knows the correct value s as well as the corrupted parties’ shares $s_{j}$ of s (these are defined by the simulators choice of the corrupted parties’s shares of $k, a, b, d, e$ ). This fixes $t + 1$ points on the a degree $2 t$ polynomial $f_{s}$ over which s is shared, and because $[s]$ includes the random zero sharing $[c]$ which effectively randomizes the polynomial, the simulator can simulate by picking a random degree $2 t$ polynomial as long as it is consistent with these $t + 1$ points.

We emphasize that the simulation is in fact perfect as it relies on no computational assumptions and works even when $Z_{q}$ and G are small.

Security. This completes our informal description of the protocol and we can state our result as follows.

Theorem 3.1 (Informal).

The described protocol for ECDSA signatures achieves perfect UC-security with abort against a static, malicious adversary corrupting at most t parties if the total number of parties n satisfies $n ⩾ 2 t + 1$ .

4. Security analysis

In this section we give a full proof of security of our basic protocol (with abort) in the UC model [7]. For completeness we also formally prove that re-running the protocol a reasonable number of times if it aborts is secure.

4.1. The formal ideal functionality and protocol

For simplicity we consider the case where the parties generate a single key pair and use this for multiple signatures. Security in the case with multiple keys follows immediately by the UC composition theorem [7]. Also, we will not divide the protocol into pre-processing and online parts. Extending the proof to handle this is straight-forward, but tedious. Finally, we will implicitly assume standard UC bookkeeping. We e.g. assume that session ids and party ids are sent along with the messages so that the ideal functionality knows to which instance a message belongs, and we assume that the functionality aborts if a party tries to reuse session ids or sends messages out of order. We also leave implicit that the functionality and the protocol are both parameterized by a single DSA/ECDSA instance $(G, g, q, H, F)$ and concrete values n and t.

We use a subscript I (as in $x_{I}$ , $y_{I}$ ) for values in the ideal functionality to emphasize that these values are correct by definition.

The ideal functionality for ECDSA, $F_{TDSA}$ , is defined in Fig. 1. In addition to the keygen and sign messages it receives from the parties $P_{i}$ , it interacts with the adversary A in what defines the “allowed” adversarial influence and leakage. Note how abort and the lack of fairness is modeled: $F_{TDSA}$ leaks the full signature $R_{I}, s_{I}$ at the beginning of sign, before any honest parties receive the output, and the adversary can abort the protocol on behalf of any of the parties $P_{i}$ at any time by sending $(ABORT, P_{i})$ to the functionality. Note also that $R_{I}$ and not $r_{I}$ is output by $F_{TDSA}$ . This simplifies the proof a bit and does not reveal anything extra, since $R_{I}$ is uniquely determined by the values $m, y_{I}, r_{I}, s_{I}$ . It is of course ok for a given application using $F_{TDSA}$ to compute $r_{I} = F (R_{I})$ and use $r_{I}, s_{I}$ instead of $R_{I}, s_{I}$ as the signature.

Fig. 1.

The ideal functionality $F_{TDSA}$ .

We continue to describe the protocol $Π_{TDSA}$ depicted in Fig. 2 and 3. Here the parties receive input from the environment E and communicate with each other. Formally, $Π_{TDSA}$ works in the $F_{COM}$ -hybrid model, where $F_{COM}$ is an ideal functionality for pairwise authentic and private channels. For simplicity we will not mention $F_{COM}$ , but just say that a message is sent to another party. In Fig. 3 the we use PRESIG to emphasize that the first rounds do not depend on the message to be signed. In the last round the signature is opened up to all parties.

Fig. 2.

The protocol $Π_{TDSA}$ (keygen).

Fig. 3.

The protocol $Π_{TDSA}$ (sign).

Theorem 1.

$Π_{TDSA}$ securely realizes $F_{TDSA}$ in the $F_{COM}$ -hybrid model against a static, malicious adversary corrupting at most t parties if the total number of parties n satisfies $n ⩾ 2 t + 1$ .

To prove Theorem 1 we must prove that for any adversary A there exists a simulator S such that for any environment E the value $\begin{array}{l} | Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1] - Pr [{IDEAL}_{F_{TDSA}, S, E} (κ) = 1] | \end{array}$ goes to zero faster than any inverse polynomial in the security parameter κ, where ${REAL}_{Π_{TDSA}, A, E} (κ)$ and ${IDEAL}_{F_{TDSA}, S, E} (κ)$ are the real and ideal executions in the UC framework [7].

We will in fact prove that $Π_{TDSA}$ realizes $F_{TDSA}$ perfectly. This means that the probability that E outputs 1 is the same in the real and the ideal execution. This means that Theorem 1 does not depend on any computational assumptions, and security does not rely on e.g. the size of q. As we will later see, this means that the only assumption is the unforgeability of the standard DSA/ECDSA signature scheme itself.

Consider first an execution ${REAL}_{Π_{TDSA}, E, A} (κ)$ . Recall that we say that a degree t sharing $[x]$ is inconsistent if the shares of the honest parties do not uniquely define a degree t polynomial and that we have no error correction on the final $WMULOPEN$ producing the signature. Let $Δ_{s}^{(i)}$ be the error that A introduces on the signature output to $P_{i}$ , i.e., $P_{i}$ receives the value $s + Δ_{s}^{(i)}$ where s is the value that would be output with no malicious behavior. Then we can define the following events in the execution:

$B_{1}$ : Some honest party P passes $Check1$ (Fig. 2) without abort and either $[x]$ is inconsistent or P receives $y^{'} \neq g^{x}$ .

$B_{2}$ : Some honest party P passes $Check3$ (Fig. 3) without abort and either $[k]$ is inconsistent or P receives $R^{'} \neq g^{k}$ .

$B_{3}$ : Some honest party P passes $Check5$ (Fig. 3) without abort and either $[a]$ is inconsistent or P receives $W^{'} \neq g^{a k}$ .

$B_{4}$ : Some honest party $P_{i}$ passes $Check9$ (final signature verification, Fig. 3), but $Δ_{s}^{(i)} \neq 0$ .

For example, $\neg B_{1}$ is the “good” event that either all honest parties abort (due to $Check1$ when computing $POWOPEN (g, [x]))$ or one or more honest parties continue past $Check1$ , but then the sharing $[x]$ is consistent and all honest parties that do get by $Check1$ without aborting agree on $y = g^{x}$ . Let B be the event that “something” bad happens, i.e., $B = B_{1} \lor B_{2} \lor B_{3} \lor B_{4}$ .

Proposition 4.1.

For any A, E it holds that $Pr [B] = 0$ in the probability space over the random coins of E, A and the honest parties in the real execution ${REAL}_{Π_{TDSA}, E, A} (κ)$ .

Proof.

The events $B_{1}, B_{2}, B_{3}, B_{4}$ are not independent. However, it follows from the argumentation in the previous section about $POWOPEN$ that $Pr [\neg B_{1}] = 1$ . (There is no way, even for an all-powerful adversary to make an honest party proceed if the honest parties’ shares of x are inconsistent. And if consistent, every honest party will either abort or output $y = g^{x}$ .) For the same reasons, $Pr [\neg B_{2} | \neg B_{1}] = 1$ . Given that all honest parties’s shares $[k]$ are consistent and they all agree on $R = g^{k}$ , the same arguments apply for the final call to $POWOPEN$ , namely $POWOPEN (g^{k}, [a])$ , so we conclude that $Pr [\neg B_{3} | \neg B_{1} \land \neg B_{2}] = 1$ .

Assuming none of the events $B_{1}, B_{2}, B_{3}$ happen we continue to analyze the probability of $B_{4}$ via the following game $G_{S-ERR}$ for an adversary $A_{S-ERR}$ :

$x, a, k, Δ_{s}, m \leftarrow A_{S-ERR} ()$

If $a k = 0$ then halt

Let $r = F (g^{k})$ , $s^{'} = a {(a k)}^{- 1} (m + r x) + Δ_{s}$ .5

⁵

Assuming correctness of $POWOPEN$ (i.e., $\neg B_{1}, \neg B_{2}, \neg B_{3}$ ), this is how s is actually computed in the protocol.

If $s^{'} = 0$ , $s^{'} = k^{- 1} (m + r x)$ or $g^{k s^{'}} \neq g^{m} y^{r}$ then halt

Output ⊤

This models that $A_{S-ERR}$ wins if he can provoke a “false” signature $s^{'} \notin {0, s}$ such that the protocol does not abort when the signature is validated by a party in the protocol.

Note that we make the (realistic) assumption that $A_{S-ERR}$ can choose the message m. In the actual protocol $x, a, k \in Z_{q}$ are guaranteed to be uniformly random and hidden from A (assuming that computing discrete logs is hard). Here, however, we allow $A_{S-ERR}$ to choose these values as he likes, only subject to $a k \neq 0$ . This only makes our argument stronger.

$A_{S-ERR}$ cannot win if $a k = 0$ or $s^{'} = 0$ . This is because the honest parties can check this and abort if so. Finally, to win, $A_{S-ERR}$ must produce a value $s^{'}$ different from the correct s, but still such that $g^{k s^{'}} = g^{m} y^{r}$ , i.e. such that the validation of $(R, s^{'}) = (g^{k}, s^{'})$ succeeds, where the correct values $g^{k}$ and y are used and $s^{'} = a {(a k)}^{- 1} (m + r x) + Δ_{s}$ . The latter models our assumption that neither $B_{1}$ , $B_{2}$ nor $B_{3}$ happen. Hence $\begin{array}{l} Pr [B_{4} | \neg B_{1} \land \neg B_{2} \land \neg B_{3}] ⩽ Pr [G_{S-ERR}^{A_{S-ERR}} (κ) = ⊤] . \end{array}$

We claim that for any adversary $A_{S-ERR}$ it holds that $\begin{array}{l} Pr [G_{S-ERR}^{A_{S-ERR}} (κ) = ⊤] = 0 . \end{array}$ To see this, assume that some $A_{S-ERR}$ makes the game output ⊤. Since $a k \neq 0$ it must hold that $k \neq 0$ and $a \neq 0$ . It follows that $\begin{array}{l} R^{s^{'}} = g^{m} y^{r} & ⟺ g^{k s^{'}} = g^{m + r x} \\ ⟺ k s^{'} = m + r x \\ ⟺ k (a {(a k)}^{- 1} (m + r x) + Δ_{s}) = m + r x (since a k \neq 0) \\ ⟺ k (k^{- 1} (m + r x) + Δ_{s}) = m + r x (since k \neq 0) \\ ⟺ m + r x + k Δ_{s} = m + r x \\ ⟺ k Δ_{s} = 0 \end{array}$

But this contradicts the fact that $k \neq 0$ and $s \neq s^{'}$ . We conclude that $Pr [\neg B_{4} | \neg B_{1} \land \neg B_{2} \land \neg B_{3}] = 1$ and hence, by the chain rule, that $\begin{array}{l} Pr [\neg B_{1} \land \neg B_{2} \land \neg B_{3} \land \neg B_{4}] = Pr [\neg B] = 1 . \end{array}$ □

Let A be an adversary. Recall that our goal is to prove that there exists a simulator S such that for any environment E the value $\begin{array}{l} | Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1] - Pr [{IDEAL}_{F_{TDSA}, S, E} (κ) = 1] | \end{array}$ goes to zero faster than any inverse polynomial in the security parameter κ. Note that $\begin{array}{l} Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1] = & Pr [B] Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1 | B] \\ + (1 - Pr [B]) Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1 | \neg B] . \end{array}$

From Proposition 4.1 we know that $Pr [B] = 0$ so it suffices to construct a simulator S such that for every E it holds that $\begin{array}{l} Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1 | \neg B] = Pr [{IDEAL}_{F_{TDSA}, S, E} (κ) = 1] . \end{array}$ In the following we construct the simulator and argue that the simulation works, given that none of the events $B_{1}, B_{2}, B_{3}, B_{4}$ happen.

4.2. The simulator

Assume w.l.o.g. that $n = 2 t + 1$ . Recall that the adversary is static, so the simulator knows from the beginning which parties are corrupted. Assume w.l.o.g. that $Good = {1, 2, \dots, t + 1}$ are the honest parties and $Bad = {t + 2, \dots, n}$ are the corrupted parties.6

⁶
We assume t corrupted parties. If less, the simulator can simply choose to corrupt additional parties in the simulation.

Recall that we use subscript I for values within $F_{TDSA}$ . We will use a mark (like $A^{'}$ and $x^{'}, y^{'}$ ) for the adversary, parties, and values in the simulation to help distinguish them from values in the real execution and $F_{TDSA}$ . We will also use a star, like $y^{*}$ , to denote patched values in the simulation.

The simulator S works as follows: It runs internally an instance of the real execution consisting of A and the parties (and $F_{COM}$ ). During simulation the simulator relays any messages between the environment E and the simulated adversary A’. The task of the simulator is to make the view of A’ indistinguishable from the view of A in the real execution, and to ensure that $A^{'}$ ’s view of the simulated execution remains consistent with the values that the environment inputs to and receives from the parties. To ensure the consistency, the simulator will need to patch some of the values in the simulation.

When S receives $(KEYGEN-START, P_{i})$ , or $(SIGN-START, P_{i}, M_{i})$ from $F_{TDSA}$ it inputs $(KEYGEN)$ or $(SIGN, M_{i})$ accordingly to $P_{i}^{'}$ in its simulation. Whenever one of the parties $P_{i}^{'}$ in the simulation aborts, S aborts on behalf of that party by sending $(ABORT, P_{i})$ to $F_{TDSA}$ . When a simulated party $P_{i}^{'}$ outputs $(KEYGEN-END, y^{'})$ S sends $(KEYGEN-END, P_{i})$ to $F_{TDSA}$ which in turn makes $F_{TDSA}$ output $y_{I}$ to E. When a simulated party $P_{i}^{'}$ outputs $(SIGN-END, R^{'}, s^{'})$ it sends $(SIGN-END, P_{i})$ to $F_{TDSA}$ , making it output $(R_{I}, s_{I})$ to E.

During the simulation the simulator acts as follows: In $KEYGEN-R1$ S just follows the protocol. For each honest $P_{i}, i \in Good$ the adversary sees only the t shares $x_{i, j}^{'}$ for $j \in Bad$ . These are uniformly distributed and can be consistent with any value x (shared via a degree t polynomial). Also, since $A^{'}$ does not learn $x_{i}$ for $i \in Good$ the secret $x = x_{1} + x_{2} + \dots + x_{n}$ remains hidden from $A^{'}$ , making this a perfect simulation.

In $KEYGEN-R2$ S simulates $POWOPEN (g, [x])$ as explained earlier: $A^{'}$ has already seen t points on a (random) degree t polynomial $f_{X}$ , namely $f_{X} (j) = x_{j}^{'}$ for $j \in Bad$ . It also knows $y_{I} = g^{x_{I}}$ which is leakage from $F_{TDSA}$ . This determines $f_{X}$ for $A^{'}$ . The last point $x_{I}$ is also unknown to S. In order to simulate consistently, it must somehow compute the patched values $y_{i}^{*} = g^{f_{X} (i)}, i \in Good$ sent from the honest to the corrupted parties in the simulation. This can be done by Lagrange interpolation “in the exponent” since S also knows $y_{I} = g^{x_{I}} = g^{f_{X} (0)}$ , i.e., the $(t + 1)$ ’th point “in the exponent”. So for $i = 1, 2, \dots, t + 1$ the simulator computes the Lagrange coefficients $λ_{0}^{i}, λ_{t + 2}^{i}, \dots, λ_{n}^{i}$ that given the $t + 1$ points $f_{X} (0), f_{X} (t + 2), \dots, f_{X} (n)$ interpolates the point $f (i)$ . S then sets $\begin{array}{l} y_{i}^{*} : = {(y_{I})}^{λ_{0}^{i}} \prod_{j = t + 2}^{n} g^{λ_{j}^{i} x_{I, j}} = g^{x_{I, i}} . \end{array}$ This ensures that the view of the adversary is consistent, in other words, ${log}_{g} y_{i}^{*}, i = 1, 2, \dots, t + 1$ are points on a uniformly random degree t polynomial $f_{X}$ subject only to $f_{X} (0) = x_{I}$ and $f_{X} (j) = x_{j}^{'}$ for $j \in Bad$ .

In $PRESIG-R1$ the simulator follows the protocol, using random polynomials $f_{K}^{'}, f_{A}^{'}, f_{B}^{'}, f_{D}^{'}, f_{E}^{'}$ . This simulation is perfect for the same reasons as in $KEYGEN-R1$ above.

In $PRESIG-R2$ S must ensure that $A^{'}$ ’s view remains consistent with the values $R_{I}, s_{I}$ . It receives $R_{I}$ from $F_{TDSA}$ and as before, for $i = 1, 2, \dots, t$ , it defines $\begin{array}{l} R_{i}^{*} : = {(R_{I})}^{λ_{0}^{i}} \prod_{j = t + 2}^{n} g^{λ_{j}^{i} k_{I, j}} = g^{k_{I, i}} . \end{array}$ and uses $R_{i}^{*}$ to patch the values sent from the honest parties $P_{i}$ to the corrupted parties.

Consider the simulation of $WMULOPEN ([a], [k]; [b])$ . Here the simulator just follows the protocol such that $A^{'}$ sees shares $w_{i}^{'} = k_{i}^{'} a_{i}^{'} + b_{i}^{'}$ . At this point the honest parties’ shares of $[a]$ , $[k]$ and $[b]$ are not guaranteed to be consistent and even if $[b]$ is a consistent degree $2 t$ polynomial it might not be a sharing of zero. But we know that the honest parties’ shares $a_{i}$ and $b_{i}$ are uniformly random. This is enough to ensure that the shares $w_{i}^{'}$ are also uniformly random and if consistent, will interpolate to something uniformly random (if inconsistent, any subset of $t + 1$ honest parties’ shares $w_{i}$ will interpolate to something random). This is enough to make the simulation perfectly indistinguishable from the real execution.

In $PRESIG-R3$ , assuming $\neg B_{2}$ , all honest parties reaching this step agree on $g^{k}$ . When computing $POWOPEN (g^{k}, [a])$ the simulator this time just follows the protocol, with no patching of the values $W_{i}^{'} = (g^{k^{'}}) a_{i}^{'}$ . $A^{'}$ then learns $R_{I} = g^{k_{I}}$ , $w^{'} = k^{'} a^{'}$ and $W^{'} = g^{k^{'} a^{'}}$ , which is indistinguishable from the real view $g^{k}, w = k a, W = g^{k a}$ since a is uniformly random and completely unknown to A. Since the protocol aborts if $R = 1$ we know that $k \neq 0$ , hence these views are in fact perfectly indistinguishable. If $[a]$ is inconsistent any subset of $t + 1$ honest parties will send shares $W_{i}^{'}$ that interpolate (in the exponent) to something uniformly random as in the real execution.

Regarding the distribution of the individual shares $k a_{i}$ , note again that the protocol requires the honest parties to abort if $R = 1$ , i.e., if $k = 0$ . So at this point $k a_{i}$ and hence $W_{i} = g^{k a_{i}}$ is uniformly random and therefore perfectly simulated by $W_{i}^{'}$ .

In $SIGN-R1$ the simulator must simulate the shares $s_{i}, i \in Good$ that the honest parties send to the corrupted parties. The simulation of $s_{i}$ is different from the simulation of $w_{i}$ above, since w was a uniformly random value internal to the protocol and no patching was needed. In contrast, the result of $WMULOPEN$ in $SIGN-R1$ has to match $s_{I}$ provided by $F_{TDSA}$ , so the simulator cannot just use $s_{i}^{'}$ but must do some patching as described here:

Assume for a moment that all honest parties agree on the message M to sign (and recall that we proved $\neg B$ ). A then expects to see shares $s_{i} = h_{i} (m + r x_{i}) + m d_{i} + e_{i}$ from the honest parties. In the worst case, the corrupted parties $P_{j}$ do not send out their shares $s_{j}$ until they have received shares $s_{i}$ from all the honest parties. The simulator must be able to simulate $s_{i}$ . Since the shares $e_{i}$ of the honest parties are guaranteed to be uniformly random, the shares $s_{i}, i \in Good$ are shares of a uniformly random degree $2 t$ polynomial $f_{s}$ subject to $f_{s} (0) = s_{I}$ and $f_{s} (j) = s_{j}^{'}, j \in Bad$ .

Recall that when the honest parties agree on M, S receives $s_{I}$ from $F_{TDSA}$ . In the special case $t = 1$ the simulator then knows $2 t + 1$ shares of $f_{s}$ , namely the $t + 1$ honest shares and $s_{I}$ , and this is enough shares to uniquely determine $f_{s}$ , so it can use $f_{s} (i), i \in Good$ as the honest parties’ shares in the simulation.

But if $t > 1$ (for example in the case $n = 5, t = 2$ ) $s_{i}^{'}, i \in Good$ and $s_{I}$ are not enough points to determine $f_{s}$ . In this case the simulation relies on the fact that S can compute the shares $s_{j}^{'}, j \in Bad$ that the corrupted parties would send to the honest parties in the simulation if they were honest. So S chooses a uniformly random degree $2 t$ polynomial $f_{s}$ subject to $f_{s} (0) = s_{I}$ and $f_{s} (j) = s_{j}, j \in Bad$ and patches the simulation such that the honest parties send $s_{i}^{*} = f_{s} (i), i \in Good$ to the corrupted parties.

In fact, since it is not guaranteed at this point that $[e]$ and $[d]$ are sharings of zero, or even consistent sharings, S chooses instead a random $f_{s}$ subject to $f_{s} (0) = s_{I}$ and $f_{s} (j) = {(a^{'} k^{'})}^{- 1} a_{j}^{'} (m + r x_{j}^{'}), j \in Bad$ (note that $a^{'}$ and $k^{'}$ are well-defined at this point since $\neg B_{2}$ and $\neg B_{3}$ and $a^{'} k^{'} \neq 0$ due to $Check6$ and $Check7$ ) and then uses $s_{i}^{*} = f_{s} (i) + d_{i}^{'} m + e_{i}^{'}, i \in Good$ in the simulation. This ensures that any errors on $[d]$ and $[e]$ are simulated as well.

Consider then the case where the honest parties do not agree on the message to sign. We claim that in this case S can simply use uniformly random values $s_{i}$ in the simulation. Assume w.l.o.g. that $n = 3, t = 1$ and that $P_{1}, P_{2}, P_{3}$ use different messages $m_{1} \neq m_{2} \neq m_{3}$ . Since $c_{i} = d_{i} m_{i} + e_{i}$ are used to blind the shares in the real execution it suffices to show that these the values $c_{i}$ are uniformly random, mutually independent values. Note that we can write $\begin{array}{l} (c_{1}, c_{2}, c_{3}) = (d_{1} m_{1} + e_{1}, d_{2} m_{1} + e_{2}, d_{3} m_{1} + e_{3}) + (0, d_{2} (m_{2} - m_{1}), d_{3} (m_{3} - m_{1})) . \end{array}$

The values $e_{1}, e_{2}$ are uniformly random and independent (unlike $e_{1}, e_{2}, e_{3}$ which are shares in a degree $2 t$ sharing if zero, so the third share is determined by the two others). So $c_{1}, c_{2}$ are uniform and independent. Since $d_{2}, d_{3}$ are uniformly random and mutually independent (also regarding $e_{i}, m_{i}$ ) the values $d_{2} (m_{2} - m_{1}), d_{3} (m_{3} - m_{1})$ ensure that all three values $c_{i}$ are uniformly random and mutually independent. Generally, with different messages, $[e]$ ensures that all but one of the shares $c_{i}$ are uniform and mutually independent, while $[d]$ ensures that the last share is also uniform and independent of the others.

The success of the simulation in $SIGN-R1$ finally depends on $\neg B_{4}$ , i.e., that the only possible value of s that can pass the final signature validation ( $Check9$ ) is indeed the value s computed by the protocol. Otherwise A could use the error $Δ_{s}$ to let the protocol output valid signatures with a distribution unknown to the simulator, which would make the simulation fail.

Finally, consider how to simulate abort. $F_{TDSA}$ gives S the power to abort on behalf of any party at any time in the ideal execution. So we simply let S abort on behalf of a party $P_{i}$ if $P_{i}^{'}$ aborts in the simulation. We have already argued that everything else is perfectly simulated, so we just need to argue that any abort in the real execution happens based on information that is available to the simulator. This ensures that abort is perfectly simulated.

To see this, note that honest parties only abort in these cases:

If $F_{COM}$ aborts

If $Check1$ (Fig. 2) fails in $KEYGEN$ (validating y)

If $Check2$ (Fig. 2) fails in $KEYGEN$ (if $y = 1$ )

If $Check3$ (Fig. 3) fails in $PRESIG-R2$ (validating R)

If $Check4$ (Fig. 3) fails in $PRESIG-R2$ (if $R = 1$ )

If $Check5$ (Fig. 3) fails in $PRESIG-R3$ (validating W)

If $Check6$ (Fig. 3) fails in $PRESIG-R3$ (if $w = 0$ )

If $Check7$ (Fig. 3) fails in $PRESIG-R3$ (if not $g^{w} = W$ )

If $Check8$ (Fig. 3) fails in $SIGN-R1$ (if $s = 0$ )

If $Check9$ (Fig. 3) fails in $SIGN-R1$ (if $R, s$ is an invalid signature of $M_{i}$ with respect to y)

In all of these cases the values are known to the simulator (such as $y, R$ ), or unknown to the environment and the distribution of the value known to the simulator (such as w and W). Hence abort can be perfectly simulated. (This is in contrast to a setting where the abort of an honest party may depend on some private input that the honest parties receive from the environment and which is therefore unknown to the simulator.)

The simulator is summarized in Fig. 4. Note that its running time is polynomial in the running time of the adversary $A^{'}$ that it simulates.

Fig. 4.

The simulator for $Π_{TDSA}$ .

This completes our argument that $\begin{array}{l} Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1 | \neg B] = Pr [{IDEAL}_{F_{TDSA}, S, E} (κ) = 1] \end{array}$ and hence the proof of Theorem 1. Note that the simulation is indeed perfect in the sense that nothing in the proof depends on computational assumptions and $Pr [{REAL}_{Π_{TDSA}, A, E} (κ) = 1]$ is not just close to, but in fact equal to $Pr [{IDEAL}_{F_{TDSA}, S, E} (κ) = 1]$ . QED

4.3. Unforgeability in the threshold case

Theorem 1 states that the protocol $Π_{TDSA}$ emulates $F_{TDSA}$ in a strong sense. Even an all-powerful adversary that can solve discrete logs or forge signatures cannot gain any other information or do any other harm than what is explicitly defined by $F_{TDSA}$ , not even when many instances of the protocol run concurrently. This means that when analyzing the security we can safely forget about the protocol and instead focus on $F_{TDSA}$ . In other words, given Theorem 1 it is sufficient to prove that no adversary with oracle access to $F_{TDSA}$ can forge signatures. The proof is a straight-forward reduction to the standard unforgeability game for signature schemes, but we include it here for completeness.

Consider the following game $G_{T-FORGE}$ :

Run an instance of $F_{TDSA}$ where A is allowed to

Provide input to and receive output from the parties

Provide the allowed adversarial input (such as $KEYGEN-END$ ) and receive the adversarial output (such as $SIGN-LEAK$ ) as defined by $F_{TDSA}$

Let $x_{I}, y_{I}$ be the key pair generated by $F_{TDSA}$ . Let Q be the set of messages that is signed by $F_{TDSA}$ (i.e., where at least one party $P_{i}$ receives the signature)

On $(FORGE, M, r^{'}, s^{'})$ from A

If $M \notin Q$ and ${Verify}_{y} (M, r^{'}, s^{'}) = ⊤$ output ⊤ and halt;

else, output ⊥ and halt

We say that $F_{TDSA}$ is existentially unforgeable if no A can make $G_{T-FORGE}$ output ⊤ except with probability negligible in κ. Note that this models the realistic setting where the adversary can influence also the messages of the honest parties.

Proposition 4.2.
Assuming that the ECDSA signature scheme used by $F_{TDSA}$ is existentially unforgeable, then $F_{TDSA}$ is existentially unforgeable.
Proof.
Proposition 4.2 is proved by the following simple reduction. Assume that $F_{TDSA}$ is not unforgeable. This means that some $A_{T-FORGE}$ wins $G_{T-FORGE}$ with non-negligible probability p. We construct an adversary $A_{FORGE}$ for the standard unforgeability game $G_{FORGE}$ (see previous section on signature schemes) as follows:
$A_{FORGE}$ runs internally an instance of $A_{T-FORGE}$ while playing the role of $G_{T-FORGE}$ .

When $A_{FORGE}$ receives the public key $y_{I}$ from $G_{FORGE}$ , it saves it for later. If $A_{T-FORGE}$ at some point inputs $(KEYGEN)$ to $t + 1$ honest parties, $A_{FORGE}$ inputs the message $(KEYGEN-LEAK, y_{I})$ to $A_{T-FORGE}$ .

Whenever $A_{T-FORGE}$ inputs $(SIGN, s i d, \cdot)$ to all parties for some session $s i d$ , if the messages differ, just input the message $(SIGN-LEAK-1, s i d, R^{'})$ for a random value $R^{'} \in G$ . If the messages are all equal (call this message M), $A_{FORGE}$ inputs $(SIGN, M)$ to $G_{FORGE}$ and receives $r, s$ . It then computes $m = H (M)$ , $R = g^{m s^{- 1}} y^{r s^{- 1}}$ and inputs $(SIGN-LEAK-1, s i d, R)$ and $(SIGN-LEAK-2, s i d, s)$ to $A_{T-FORGE}$ .

On $(FORGE, M^{'}, r^{'}, s^{'})$ from $A_{T-FORGE}$ , the adversary $A_{FORGE}$ outputs the message $(FORGE, M^{'}, r^{'}, s^{'})$ to $G_{FORGE}$ .

It is clear from this construction that the running time of $A_{FORGE}$ is polynomial in the running time of $A_{T-FORGE}$ and that $A_{FORGE}$ wins $G_{FORGE}$ with the same non-negligible probability p. (If the messages to the signing session differ, $g^{k}$ is leaked, but this is perfectly simulated by $R^{'}$ .) This contradicts the assumption that the underlying ECDSA scheme is unforgeable. □

4.4. On the lack of termination guarantee

Recall that contrary to Gennaro et al. [22,24] we allow a single corrupt party to abort the protocol at any time, and that this ability is also built into $F_{TDSA}$ .

In practice, when key generation aborts, the parties will usually start from scratch, trying to generate a new key. And if signing aborts, they will usually retry signing with the same key, but with a fresh randomizer k. Only after retrying a reasonable number of times will the protocol be aborted totally. In this sense, $F_{TDSA}$ does not fully model real usage, since it allows only “one shot” at generating the key and doing a signature.

Recall that the adversary learns $g^{x}$ and $g^{k}$ and may abort on these values. Intuitively, allowing the protocol to rerun L times on abort is therefore equivalent to letting the adversary “decide” ${log}_{2} L$ bits of $g^{x}$ and $g^{k}$ . This is different from the basic DSA/ECDSA standard that states that x and k should be chosen uniformly at random.

However, it can be shown that retrying a reasonable number of times on abort, thereby allowing the adversary to decide a few bits of $g^{x}$ and $g^{y}$ , does not harm security. We include the proof here for completeness.

Consider the game $G_{R}$ that works as $G_{T-FORGE}$ , but where the adversary in addition can request that the signature generation is rerun with the same key $x_{I}$ but a new randomizer $k_{I}^{'}$ (and a new message), and hence $(SIGN-LEAK-1, g^{k^{'} I})$ and $(SIGN-LEAK-2, s_{I}^{'})$ is output to the adversary. This models the realistic setting where the adversary causes the sign protocol rerun on abort. But intuitively, this gives the adversary no additional power since it already has the power to request a new signature generation by inputting $(SIGN, \cdot)$ to the parties.

Proposition 4.3.
For any $A_{R}$ with running time t there exists an adversary $A_{T-FORGE}$ with running time polynomial in t such that $Pr [G_{T-FORGE}^{A_{T-FORGE}} = ⊤] = Pr [G_{R}^{A_{R}} = ⊤]$ .
Proof.
The reduction is simple: Given $A_{R}$ that wins $G_{R}$ with non-negligible probability $p_{R}$ we can construct $A_{T-FORGE}$ as follows: $A_{T-FORGE}$ runs internally $A_{R}$ . If $A_{R}$ requests that signature generation is rerun, $A_{T-FORGE}$ instead inputs $(SIGN, s i d, M)$ to the parties in $G_{T-FORGE}$ using a fresh session identifier. It then receives the message $(SIGN-LEAK-1, g^{k})$ and $(SIGN-LEAK-2, s)$ from $F_{TDSA}$ in $G_{T-FORGE}$ and forwards these messages to $A_{R}$ . From this construction it is clear that $A_{T-FORGE}$ wins $G_{T-FORGE}$ with exactly the same probability $p_{R}$ . □

We finally consider the even more realistic setting where the protocol may also be rerun up to M times during key generation. We model this by the following game $G_{YR}$ against an adversary $A_{YR}$ :

As $G_{R}$ the game $G_{YR}$ runs internally an instance of $F_{TDSA}$ . $A_{YR}$ gets to decide the input to the parties and the adversarial input to $F_{TDSA}$ , and $A_{YR}$ gets to see the parties’ output and the adversarial leakage from $F_{TDSA}$ . It can also cause the signing phase to be re-run as in $G_{R}$ .

$G_{YR}$ accepts an additional message $RESET-KEYGEN$ from $A_{YR}$ :7
⁷
We could also have defined this game such that it restarted keygen on abort (as in the real setting), but it is just as powerful to simply allow the adversary to reset the functionality using an explicit command.

If more than L of these messages have been received, $G_{YR}$ halts; If any honest party have already output $(KEYGEN-END, \cdot)$ in the current instance of $F_{TDSA}$ then $G_{YR}$ outputs ⊥ and halts;8
⁸
At this point in the real execution, each honest party knows that the key generation was successful and that all honest parties holds the correct public key, so they can safely refuse any rerun of keygen at this point.

Otherwise, $G_{YR}$ deletes the current instance of $F_{TDSA}$ and starts a completely new $F_{TDSA}$ instance using fresh randomness.

As in $G_{R}$ the adversary $A_{YR}$ is allowed to send the message $(FORGE, M^{'}, r^{'}, s^{'})$ . For $i = 1, 2, \dots, L$ let $y_{I}^{(i)}$ be the (up to) L public keys produced by the L instances of $F_{TDSA}$ and let $Q^{(i)}$ be the set of messages for which a signature was output to a party using $y_{I}^{(i)}$ . $G_{YR}$ outputs ⊤ on $(FORGE, M^{'}, r^{'}, s^{'})$ only if there is an i such that $M^{'} \notin Q^{(i)} \land {Verify}_{y^{(} i)_{I}} (M^{'}, r^{'}, s^{'}) = ⊤$ . (That is, to win $G_{YR}$ it is enough to be able to forge with respect to any of the public keys.)

We say that $F_{TDSA}$ is unforgeable with retries if no adversary $A_{YR}$ wins $G_{YR}$ except with negligible probability.
Proposition 4.4.
For any $A_{YR}$ with running time t there exists an adversary $A_{R}$ with running time polynomial in t such that $\begin{array}{l} Pr [G_{R}^{A_{R}} = ⊤] ⩾ \frac{1}{L} \cdot Pr [G_{YR}^{A_{YR}} = ⊤] . \end{array}$
Proof.
Let $A_{YR}$ be an adversary for $G_{YR}$ , i.e. $A_{YR}$ can interact with $G_{YR}$ and then output $M^{'}, r^{'}, s^{'}$ such that $r^{'}, s^{'}$ is a valid signature on $M^{'}$ relative to one of the keys generated internally in $G_{YR}$ .

We construct an $A_{R}$ as follows:
$A_{R}$ runs internally an instance of $A_{YR}$ . Recall that $A_{R}$ can only interact with $A_{YR}$ via the interface defined by $G_{YR}$ .

$A_{R}$ forwards any adversarial influence (such as $KEYGEN-END$ , $SIGN-END$ ) and any input to the parties (such as messages to sign) from $A_{YR}$ to $G_{R}$ . Any adversarial leakage from $G_{R}$ is forwarded to $A_{R}$ .

The only situation where $A_{R}$ cannot naturally forward messages is when $A_{YR}$ sends the $KEYGEN-RESET$ message. To handle this, when $A_{R}$ receives the message $(KEYGEN-LEAK, y_{I})$ from $G_{R}$ (this happens at most once), $A_{R}$ creates a set of public keys PK consisting of $y_{I}$ and $L - 1$ random dummy keys $y_{1}^{'}, \dots, y_{L - 1}^{'}$ . When receiving $(KEYGEN-RESET)$ $A_{R}$ removes a random key y from PK and sends $(KEYGEN-LEAK, y)$ to $A_{YR}$ .

Let E be the event that $A_{YR}$ does not send another $KEYGEN-RESET$ message after receiving $(KEYGEN-LEAK, y_{I})$ . That is, E is the event that $A_{YR}$ “accepts” the real public key $y_{I}$ and not one of the dummy keys for signing. Then, it is clear that by construction we have $Pr [G_{R}^{A_{R}} = ⊤ | E] = Pr [G_{YR}^{A_{YR}}]$ . Also, since there are L keys in PR and $A_{R}$ removes keys from PK at random, $Pr [E] = 1 / L$ . Hence $\begin{array}{l} Pr [G_{R}^{A_{R}} = ⊤ | E] & = Pr [G_{R}^{A_{R}} = ⊤ \cap E] / Pr [E] \\ = L \cdot Pr [G_{R}^{A_{R}} = ⊤ \cap E] \\ ⩽ L \cdot Pr [G_{R}^{A_{R}} = ⊤] . \end{array}$ □
Theorem 4.1.
If the DSA/ECDSA signature scheme used by $F_{TDSA}$ is existentially unforgeable then $F_{TDSA}$ is unforgeable with retries.
Proof.
Assume that some adversary $A_{YR}$ wins $G_{YR}$ with non-negligible probability p. Then by Proposition 4.3 and Proposition 4.4 there exists an adversary $A_{T-FORGE}$ that runs in polynomial time in the running time of $A_{YR}$ and that wins $G_{T-FORGE}$ with probability at least $p / L$ . Then, by Proposition 4.2 there exists an adversary $A_{FORGE}$ with running time polynomial in the running time of $A_{T-FORGE}$ that wins $G_{FORGE}$ with probability $p / L$ . This contradicts the unforgeability of the signature scheme used by $F_{TDSA}$ . □

Since by Theorem 1 the ideal execution with $F_{TDSA}$ perfectly emulates the real protocol execution, we conclude that no adversary for our threshold protocol can succeed in forging signatures with more than probability $L \cdot p$ where p is the probability that an adversary can forge signatures in the standard DSA/ECDSA signature scheme.
5. Guaranteed output delivery in the online phase

Unlike Gennaro et al. [22] (but like the ECDSA protocols for dishonest majority [17,20,31–33]) our basic protocol described above has no fairness or guaranteed output delivery. So the adversary gets to see the signature $r, s$ and may then abort the protocol before any honest party receives the signature. In practice, parties will retry on abort and the adversary may therefore end up with several valid signatures $(r_{1}, s_{1}), \dots (r_{L}, s_{L})$ on message M without any of the honest parties knowing any of these signatures.

This is of course not a forgery, since it can only happen with messages that the honest parties actually intended to sign. But it may nevertheless be unacceptable in some applications. For example if presenting a fresh signature allows to transfer a certain additional amount of money from someone’s bank account.

Since we assume an honest majority it is indeed possible to achieve guaranteed output delivery (and hence also fairness). In fact, our basic protocol can be extended with just a few additional pre-processing rounds in order to achieve this. The main idea is that in addition to R and $[k^{- 1}]$ the parties also prepare a sharing of $[x \cdot k^{- 1}]$ in the pre-processing. Doing so, $[s]$ can be computed as $[s] = m [k^{- 1}] + r [x k^{- 1}]$ , using only linear operations. Taking this one step further, by reducing the degree of $[x \cdot k^{- 1}]$ to t and turning both $[k^{- 1}]$ and $[x k^{- 1}]$ into suitable verifiable secret sharings [35], we achieve the property that online, when M is known, the signature can be computed given only $t + 1$ correct shares and the correctness of each share can be validated.

The extended protocol works as follows. Let ${[[a]]}_{t}$ denote a verifiable secret sharing (VSS) of a, that is, every party is committed to his share of a via a Pedersen commitment, and shares are guaranteed to be consistent with a polynomial of degree at most t. Such sharings are additive, we have $[[a]] + [[x]] = [[a + x]]$ , where addition denotes local addition of shares and commitment opening data [35].

To create a verifiable secret sharing ${[[s]]}_{t}$ , a party P commits to the coefficients of a polynomial f of degree at most t, including a commitment to s that plays the role of the degree 0 coefficient. Now anyone can compute a commitment to $f (i)$ for $i = 1 \dots n$ using the homomorphic property of commitments. P sends privately opening information for this commitment to $P_{i}$ . In the next round, $P_{i}$ will complain if what he gets does not match his commitment.

Using this in the context of our threshold signature protocol, we can assume that we have ${[[x]]}_{t}$ once and for all from the key generation phase. Using our protocol as described before, we can create r and $[k^{- 1}]$ . Now, the goal of the following subprotocol is to start from ${[[x]]}_{t}$ and $[k^{- 1}]$ and obtain ${[[x \cdot k^{- 1}]]}_{t}$ and ${[[k^{- 1}]]}_{t}$ .

So we do the following:

At the start of the entire protocol, each party will send his contribution to create one VSS of a random value ${[[b]]}_{t}$ as described above, to all other parties.

In the following round, the object ${[[b]]}_{t}$ can be computed (or we abort). Therefore we can assume that when $[k^{- 1}]$ is ready, the VSS of b is also ready. We can also assume that each party $P_{i}$ has committed to his share $k_{i}$ in $k^{- 1}$ , as he can do this as soon as he knows this share.

Now, each $P_{i}$ opens the difference between $k_{i}$ and his share of b to all parties.

If the set of opened differences are consistent with a degree t polynomial, we continue, else we abort. Adjust the commitments to shares in ${[[b]]}_{t}$ using the opened differences to get ${[[k^{- 1}]]}_{t}$ (only local computation). Now each party creates a VSS ${[[x_{i} \cdot (k_{i}^{- 1})]]}_{t}$ of the product of his share in $k^{- 1}$ and in x. He includes a standard ZK proof that the comitted zero-coefficient of this VSS is indeed correct (this can be done since we already have ${[[x]]}_{t}$ and ${[[k^{-} 1]]}_{t}$ ).

Using suitable Lagrange coefficients $λ_{i}$ the parties can now locally compute $\begin{array}{l} {[[k^{- 1} x]]}_{t} = λ_{1} {[[k_{1}^{- 1} \cdot x_{1}]]}_{t} + \dots + λ_{n} {[[k_{n}^{- 1} \cdot x_{n}]]}_{t} . \end{array}$

Finally, each party broadcasts a hash of his public view of the protocol so far (i.e., all the messages that he received and which were supposed to be sent to all parties) together with “OK” if he thinks the protocol went well so far. Each party aborts unless he gets an “OK” from all other parties and the hash of his own public view matches the hashes he receives from all other parties.9

⁹
Note that a real broadcast is required here, since all honest parties need to agree that the pre-processing went well. Otherwise, we risk that a few honest parties may proceed to the online phase which will then abort, and so we no longer have guaranteed output delivery in the online phase.

Given this, once the message M is known, the parties can compute $m = H (M)$ and $\begin{array}{l} {[[s]]}_{t} = m \cdot {[[k^{- 1}]]}_{t} + r \cdot {[[x \cdot k^{- 1}]]}_{t} \end{array}$ using only local operations. To output the signature $(r, s)$ each party sends r along with its share of s and the corresponding commitment opening to the receiver. Since the degree of ${[[s]]}_{t}$ is t the receiver only needs $t + 1$ correct shares, and by verifying the commitment of each share, the receiver knows which shares are correct. Since we assume $n ⩾ 2 t + 1$ we know that at least $t + 1$ parties are honest, and thus the receiver is guaranteed to get the signature.

In other words, we get the desired property that either the protocol aborts during pre-processing and neither the adversary nor any other party gets the signature, or intended receiver(s) are guaranteed to get the signature.10

¹⁰

It still holds that no interaction is required among the parties in the online phase. But the trick used in our basic protocol of blinding $[s]$ with $m [d] + [e]$ only works for degree $2 t$ sharings. So unlike our basic protocol, we here require that the honest parties agree on M.

6. Performance

In this section we elaborate the performance of our basic protocol (with abort).

The protocol requires four rounds of interaction between the servers to generate a signature. But the first three rounds can be executed before the message to be signed is known.

We let a presignature denote the value R and the sharings $[k^{- 1}], [e], [d]$ produced during the first three rounds. Each party can save R and its shares of $k^{- 1}, e, d$ under a unique presignature id (such as R). When the message M is known, the parties need only then agree on a presignature id in order to complete the signature protocol in one round.

The protocol is designed to run with any number of $n ⩾ 2 t + 1$ parties. Recall that a random element $r \in Z_{q}$ can be represented using ${log}_{2} q$ bits and an element in $G \subset Z_{p} \times Z_{p}$ using ${log}_{2} p$ bits (roughly) using point compression. The protocol is constant-round and the communication complexity is $O (κ n^{2})$ assuming that both $log p$ and $log q$ are proportional to a security parameter κ.

For a small number of parties, unless special hardware acceleration is available, the computational bottleneck is likely to be the “long” curve exponentiations, i.e., computing $g^{r}$ for ${log}_{2} (q)$ -bit values $r \in Z_{q}$ . In our case, each party must do five long exponentiations (one for each of the two POWOPENs, one for $g^{w} = W$ , and two for verifying the final signature).

In addition, in POWOPEN a party uses the first $t + 1$ values received to verify the remaining $n - (t + 1)$ shares using Lagrange interpolation in the exponent. This involves $(n - t + 1) \cdot (t + 1)$ exponentiations. Counting these as long exponentiations, we get a total of $2 t^{2} + 2 t + 5$ long exponentiations per party. Counting Lagrange interpolation in the exponent as “long” exponentiations makes sense asymptotically, though for small parameters such as $(n, t) = (3, 1)$ the Lagrange coefficent exponets are small values ( $λ_{1} (0) = - 1, λ_{2} (0) = 2$ ). Table 1 summarizes the performance.

Comparing to the (implicit) protocol in GJKR that works for $n ⩾ 2 t + 1$ with abort, we note that this requires $t^{2} + 30 t + 9$ long exponentiations. This means, for example, that for $(n, t) = (3, 1)$ GJKR requires 40 long exponentiations whereas we require only 5 (13%), if we do not count the Lagrange interpolation using coefficients $- 1$ and 2 as long exponentiations.

Table 1
Concrete performance

Protocol Bits sent per party Long exponentiations per party

$KEYGEN$ $n log q + n log p$ 1 (and $t^{2} + t$ Lagrange exp)

$PRESIG$ $6 n log q + 2 n log p$ 3 (and $2 t^{2} + 2 t$ Lagrange exp)

$SIGN$ $n log q$ 2

Protocol	Bits sent per party	Long exponentiations per party
$KEYGEN$	$n log q + n log p$	1 (and $t^{2} + t$ Lagrange exp)
$PRESIG$	$6 n log q + 2 n log p$	3 (and $2 t^{2} + 2 t$ Lagrange exp)
$SIGN$	$n log q$	2

For large n, since the protocol is constant round, the $O (n^{2})$ amount of arithmetics in $Z_{q}$ that each does, will eventually become the bottleneck. In this case, a more efficient protocol can be obtained by using hyperinvertible matrices [2] to improve performance of $RSS$ and the (passively secure) multiplication of w and s. Note however, that $O (n^{2})$ communication is still required for $POWOPEN$ .

For small n we can save bandwidth and one round by computing the sharings $[k], [a], [b], [d], [e]$ using pseudo-random secret sharing [13].

6.1. Benchmarks

In order to determine the actual performance of our protocol we have implemented it and run a number of benchmarks. We have done several things to ensure that our benchmarks best reflect a real deployment scenario.

First, we benchmark the client-server setting where we include the time it takes for an external client to initiate the protocol by sending a request to the parties and receive a response when the operation is done. Also, we ensure that the parties are connected with secure channels. Note that this requires an additional round trip and computation for key agreement using mechanisms from the Noise Protocol framework [36]. We also let each party store its key shares in encrypted form in a PostgreSQL database. For elliptic curve operations we use OpenSSL v1.1.1b which provides the required timing attack resistant implementation for long curve multiplications. However when no secret values are involved we use the faster version also provided by OpenSSL. In the latter case we use precomputation to speed up the curve multiplication when using the default generator for the given elliptic curve.

Finally, as mentioned above, we split the protocol up in pre-processing and online processing. Hence we benchmark the individual operations (1) keygen, (2) presig, and (3) sign.

Latency. For a threshold signature scheme to be useful in practice it is important that a user should not be forced to wait for minutes before his key is generated or before he receives the signature that he requested.

To measure the latency we deploy each party on a separate m5.xlarge Amazon EC2 instance. Each instance runs CoreOS with two Docker containers: One with the actual implementation of the threshold protocol party, implemented in Java, and another container with a PostgreSQL instance for storing key and presignature shares.

We then let a single client issue a single requests to the servers, causing the servers to generate a single key, presignature or signature. In this benchmark, the servers are configured to use a single worker thread, i.e., each server uses only one CPU core for executing the protocol (including computing the long curve multiplications).

We run this benchmark for various combinations of parties and security thresholds, in both the LAN setting and the WAN setting. In the LAN setting all servers are located in the same Amazon region, where the network latency is usually less than 1 ms, whereas in the WAN setting the servers are located in different regions (Frankfurt, California, Tokyo) where package latency is often in the order of 50-200 ms.11

¹¹

In the WAN setting, since we use only three different regions, with $n > 3$ this means that some of the parties run in the same region. However, since the overall latency of the protocol is determined by the pair-wise connection with the largest latency, this makes no difference.

Table 2 shows the average time it takes for the keygen, presig and sign requests to finish in these settings after a number of warm-up requests. In the keygen operation, a client sends a keygen request to the servers, which run the keygen protocol and return a key id to the client. In the presig operation, a client sends a presig request to the servers which then generate the presignature and return a presignature id to the client. In the sign operation, the client sends a key id and a presignature id to the servers (for a key and a presignature that have previously been generated), and the servers then compute and return their signature shares to the client who recombines and verifies the signature.

It can be seen that in the LAN setting the latency increases with the number of parties and the security threshold. This is because the amount of work, especially the number of long curve multiplications that each party must compute, increases (quadratically) with the number of parties, and with low network latency, this is significant for the overall latency. In the WAN setting, however, the network latency is high enough that it almost completely dominates the overall latency. (At least for up to 9 parties. Adding parties, the latency caused by local computation will eventually dominate also in the WAN setting.)

Table 2

Latency per operation

	LAN			WAN

$n, t$	keygen	presig	sign	keygen	presig	sign
$3, 1$	28.2 ms	34.2 ms	19.9 ms	1.22 s	1.47 s	0.73 s
$5, 2$	39.9 ms	44.8 ms	25.0 ms	1.47 s	1.71 s	0.98 s
$7, 3$	54.6 ms	60.0 ms	30.8 ms	1.48 s	1.72 s	0.98 s
$9, 4$	66.4 ms	74.0 ms	34.8 ms	1.48 s	1.72 s	1.00 s

Throughput. In realistic deployments, as mentioned above, a threshold signature scheme like ours will often run in the client-server setting with many concurrent key generation and signature protocol instances on behalf of clients. We therefore measure the throughput, that is, the number of operations that the servers can handle per second in this setting.

It is likely that signing will happen more often than key generation. If for example BIP-32 key derivation [41] is used, key generation is only run once to obtain a sharing of the master key whereas subsequent keys are derived in an efficient non-interactive manner.

Also, given already computed presignatures, generating the final signature is a lightweight operation for the servers, since signing for the servers then only imply a few local operations in $Z_{q}$ and sending a share of s to the client who verifies it. For these reasons, in a real deployment, we expect that presignature generation will be the overall bottleneck with respect to throughput. We therefore focus on presignature generation in this benchmark.

We run this benchmark with tree servers ( $n = 3$ ) and security threshold $t = 1$ . To best reflect an actual real-world deployment, each server consists of a load balancer (haproxy), a database server (PostgreSQL), and a number of worker hosts. Clients contact the load balancer using a secure channel. The load balancer ensures that the workload is distributed evenly among the workers based on the key id. All workers connect to the database server where the key shares are stored in encrypted form. Load balancer, database server and workers as well as all clients run on separate m5.xlarge Amazon EC2 instances (4 vCPUs, 16 GiB memory) in the same Amazon region.

Figure 5 illustrates this deployment: A client requests a presignature by contacting the three servers. Based on the given key id, one worker at each server is assigned the task (marked with bold lines). These workers then execute the presignature generation protocol and returns the presignature id to the client.

Fig. 5.

A deployment in the client-server setting with three servers and two workers per server.

To benchmark, once the servers are ready, we spin up enough clients, each client sending a lot of presig requests to the server, such that the servers are completely busy and no increase in throughput is achieved by adding more clients. Table 3 shows the resulting throughput in the case where each client requests a single presignature per request as well as in the case where each client requests 100 presignatures in per request.

Table 3

Throughput for presignature generation

Workers per server	1 presig per request	100 presigs per request
2	347 presig/s	1,249 presig/s
4	649 presig/s	2,464 presig/s
6	919 presig/s	3,606 presig/s

As expected, throughput scales almost linearly with the number of workers used by each server.

On m5.xlarge we have benchmarked that each (timing attack resistant) long curve multiplication occupies a core (i.e., 2 vCPU) for roughly 0.5 ms. Since each presig requires three multiplication, if these were the only thing to compute, we would expect 2 multiplications per ms or 666 presig/s.

In the batched setting where 100 presignatures are computed per client request, we are close to this limit and the bottleneck clearly is the CPU required to do the long curve multiplications, getting a throughput of roughly 600 presig/s. Thus, for each additional m5.xlarge worker, the system can handle roughly 600 extra presignatures per second.

In the case where only a single presignature is computed per request, the throughput is lower, since the servers must spend a larger fraction of their resources by handling the many active sessions. In this case each worker can handle roughly 150 additional presigs per second.

References

Andresen, BIP-11: M-of-N Standard Transactions, https://github.com/bitcoin/bips/blob/master/bip-0011.mediawiki, accessed: 2020-11-15.

Beerliová-Trubíniová and

Hirt, Perfectly-secure MPC with linear communication complexity, in: Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19–21, 2008

Canetti, ed., Lecture Notes in Computer Science, Vol. 4948, Springer, 2008, pp. 213–230. doi:10.1007/978-3-540-78524-8_13.

Ben-Or,

Goldwasser and

Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, May 2–4, 1988,

Simon, ed., ACM, 1988, pp. 1–10. doi:10.1145/62212.62213.

Boneh,

Gennaro and

Goldfeder, Using Level-1 Homomorphic Encryption To Improve Threshold DSA Signatures For Bitcoin Wallet Security, 2017.

Boyle,

Couteau,

Gilboa,

Ishai,

Kohl,

Rindal and

Scholl, Efficient two-round OT extension and silent non-interactive secure computation, in: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, CCS 2019, London, UK, November 11–15, 2019,

Cavallaro,

Kinder,

Wang and

Katz, eds, ACM, 2019, pp. 291–308. doi:10.1145/3319535.3354255.

D.R.L.

Brown, Generic groups, collision resistance, and ECDSA, Des. Codes Cryptography35(1) (2005), 119–152, http://www.springerlink.com/index/10.1007/s10623-003-6154-z . doi:10.1007/s10623-003-6154-z.

Canetti and

Fischlin, Universally composable commitments, in: Advances in Cryptology – CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 19–23, 2001,

Kilian, ed., Lecture Notes in Computer Science, Vol. 2139, Springer, 2001, pp. 19–40. doi:10.1007/3-540-44647-8_2.

Canetti,

Gennaro,

Goldfeder,

Makriyannis and

Peled, UC non-interactive, proactive, threshold ECDSA with identifiable aborts, in: CCS’20: 2020 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, USA, November 9–13, 2020,

Ligatti,

Ou,

Katz and

Vigna, eds, ACM, 2020, pp. 1769–1787. doi:10.1145/3372297.3423367.

Castagnos,

Catalano,

Laguillaumie,

Savasta and

Tucker, Two-party ECDSA from hash proof systems and efficient instantiations, in: Advances in Cryptology – CRYPTO 2019 – 39th Annual International Cryptology Conference, Proceedings, Part III, Santa Barbara, CA, USA, August 18–22, 2019,

Boldyreva and

Micciancio, eds, Lecture Notes in Computer Science, Vol. 11694, Springer, 2019, pp. 191–221. doi:10.1007/978-3-030-26954-8_7.

10.

Castagnos,

Catalano,

Laguillaumie,

Savasta and

Tucker, Bandwidth-efficient threshold EC-DSA, in: Public-Key Cryptography – PKC 2020 – 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings, Part II, Edinburgh, UK, May 4–7, 2020,

Kiayias,

Kohlweiss,

Wallden and

Zikas, eds, Lecture Notes in Computer Science, Vol. 12111, Springer, Edinburgh, UK, 2020, pp. 266–296. doi:10.1007/978-3-030-45388-6_10.

11.

Chaum,

Crépeau and

Damgård, Multiparty unconditionally secure protocols (extended abstract), in: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, May 2–4, 1988,

Simon, ed., ACM, 1988, pp. 11–19. doi:10.1145/62212.62214.

12.

Chida,

Genkin,

Hamada,

Ikarashi,

Kikuchi,

Lindell and

Nof, Fast large-scale honest-majority MPC for malicious adversaries, in: Advances in Cryptology – CRYPTO 2018 – 38th Annual International Cryptology Conference, Proceedings, Part III, Santa Barbara, CA, USA, August 19–23, 2018,

Shacham and

Boldyreva, eds, Lecture Notes in Computer Science, Vol. 10993, Springer, 2018, pp. 34–64. doi:10.1007/978-3-319-96878-0_2.

13.

Cramer,

Damgård and

Ishai, Share conversion, pseudorandom secret-sharing and applications to secure computation, in: Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Proceedings, Cambridge, MA, USA, February 10–12, 2005

Kilian, ed., Lecture Notes in Computer Science, Vol. 3378, Springer, 2005, pp. 342–362. doi:10.1007/978-3-540-30576-7_19.

14.

A.P.K.

Dalskov,

Keller,

Orlandi,

Shrishak and

Shulman, Securing DNSSEC keys via threshold ECDSA from generic MPC, IACR Cryptology ePrint Archive2019 (2019), 889, https://eprint.iacr.org/2019/889 .

15.

Desmedt, Society and group oriented cryptography: A new concept, in: Advances in Cryptology – CRYPTO’87, a Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Santa Barbara, California, USA, August 16–20, 1987,

Pomerance, ed., Lecture Notes in Computer Science, Vol. 293, Springer, 1987, pp. 120–127. doi:10.1007/3-540-48184-2_8.

16.

Desmedt and

Frankel, Threshold cryptosystems, in: Advances in Cryptology – CRYPTO’89, 9th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 20–24, 1989,

Brassard, ed., Lecture Notes in Computer Science, Vol. 435, Springer, 1989, pp. 307–315. doi:10.1007/0-387-34805-0_28.

17.

Doerner,

Kondi,

Lee and

Shelat, Secure two-party threshold ECDSA from ECDSA assumptions, in: 2018 IEEE Symposium on Security and Privacy, SP 2018, ProceedingsSan Francisco, California, USA, 21–23 May 2018, IEEE Computer Society, 2018, pp. 980–997. doi:10.1109/SP.2018.00036.

18.

Doerner,

Kondi,

Lee and

Shelat, Threshold ECDSA from ECDSA assumptions: The multiparty case, in: 2019 IEEE Symposium on Security and Privacy, SP 2019, San Francisco, CA, USA, May 19–23, 2019, IEEE, 2019, pp. 1051–1066. doi:10.1109/SP.2019.00024.

19.

Gagol,

Kula,

Straszak and

Swietek, IACR cryptol. ePrint arch., Threshold ECDSA for Decentralized Asset Custody2020 (2020), 498. https://eprint.iacr.org/2020/498.

20.

Gennaro and

Goldfeder, Fast multiparty threshold ECDSA with fast trustless setup, in: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15–19, 2018,

Lie,

Mannan,

Backes and

Wang, eds, ACM, 2018, pp. 1179–1194. doi:10.1145/3243734.3243859.

21.

Gennaro,

Goldfeder and

Narayanan, Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security, in: Applied Cryptography and Network Security – 14th International Conference, ACNS 2016, Proceedings, Guildford, UK, June 19–22, 2016,

Manulis,

Sadeghi and

Schneider, eds, Lecture Notes in Computer Science, Vol. 9696, Springer, Guildford, UK, 2016, pp. 156–174. doi:10.1007/978-3-319-39555-5_9.

22.

Gennaro,

Jarecki,

Krawczyk and

Rabin, Robust threshold DSS signatures, in: Advances in Cryptology – EUROCRYPT’96, International Conference on the Theory and Application of Cryptographic Techniques, Proceeding, Saragossa, Spain, May 12–16, 1996,

U.M.

Maurer, ed., Lecture Notes in Computer Science, Vol. 1070, Springer, 1996, pp. 354–371. doi:10.1007/3-540-68339-9_31.

23.

Gennaro,

Jarecki,

Krawczyk and

Rabin, Secure distributed key generation for discrete-log based cryptosystems, in: Advances in Cryptology – EUROCRYPT’99, International Conference on the Theory and Application of Cryptographic Techniques, Proceeding, Prague, Czech Republic, May 2–6, 1999,

Stern, ed., Lecture Notes in Computer Science, Vol. 1592, Springer, 1999, pp. 295–310. doi:10.1007/3-540-48910-X_21.

24.

Gennaro,

Jarecki,

Krawczyk and

Rabin, Robust threshold DSS signatures, Inf. Comput.164(1) (2001), 54–84. doi:10.1006/inco.2000.2881.

25.

Gilboa, Two party RSA key generation, in: Advances in Cryptology – CRYPTO’99, 19th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 15–19, 1999,

M.J.

Wiener, ed., Lecture Notes in Computer Science, Vol. 1666, Springer, 1999, pp. 116–129. doi:10.1007/3-540-48405-1_8.

26.

Goldreich,

Micali and

Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, in: Proceedings of the 19th Annual ACM Symposium on Theory of Computing,

A.V.

Aho, ed., ACM, New York, New York, USA, 1987, pp. 218–229. doi:10.1145/28395.28420.

27.

Johnson,

Menezes and

S.A.

Vanstone, The elliptic curve digital signature algorithm (ECDSA), Int. J. Inf. Sec.1(1) (2001), 36–63. doi:10.1007/s102070100002.

28.

Katz and

Lindell, Introduction to Modern Cryptography, 2nd edn, CRC Press, 2014. ISBN 9781466570269.

29.

Keller,

Orsini and

Scholl, MASCOT: Faster malicious arithmetic secure computation with oblivious transfer, in: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24–28, 2016,

E.R.

Weippl,

Katzenbeisser,

Kruegel,

A.C.

Myers and

Halevi, eds, ACM, 2016, pp. 830–842. doi:10.1145/2976749.2978357.

30.

C.F.

Kerry,

Secretary and

C.R.

Director, FIPS PUB 186-4 Federal Information Processing Standards Publication: Digital Signature Standard (DSS), 2013.

31.

Lindell, Fast secure two-party ECDSA signing, in: Advances in Cryptology – CRYPTO 2017 – 37th Annual International Cryptology Conference, Proceedings, Santa Barbara, CA, USA, August 20–24, 2017,

Katz and

Shacham, eds, Lecture Notes in Computer Science, Vol. 10402, Springer, 2017, pp. 613–644. doi:10.1007/978-3-319-63715-0_21.

32.

Lindell and

Nof, Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody, in: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15–19, 2018,

Lie,

Mannan,

Backes and

Wang, eds, ACM, 2018, pp. 1837–1854. doi:10.1145/3243734.3243788.

33.

P.D.

MacKenzie and

M.K.

Reiter, Two-party generation of DSA signatures, in: Advances in Cryptology – CRYPTO 2001, 21st Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 19–23, 2001,

Kilian, ed., Lecture Notes in Computer Science, Vol. 2139, Springer, 2001, pp. 137–154. doi:10.1007/3-540-44647-8_8.

34.

Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: Advances in Cryptology – EUROCRYPT’99, International Conference on the Theory and Application of Cryptographic Techniques, Proceeding, Prague, Czech Republic, May 2–6, 1999,

Stern, ed., Lecture Notes in Computer Science, Vol. 1592, Springer, 1999, pp. 223–238. doi:10.1007/3-540-48910-X_16.

35.

T.P.

Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in: Advances in Cryptology – CRYPTO’91, 11th Annual International Cryptology Conference, Proceedings, Santa Barbara, California, USA, August 11–15, 1991,

Feigenbaum, ed., Lecture Notes in Computer Science, Vol. 576, Springer, 1991, pp. 129–140. doi:10.1007/3-540-46766-1_9.

36.

Perrin, The Noise protocol framework, 2015.

37.

Shamir, How to share a secret, Commun. ACM22(11) (1979), 612–613. doi:10.1145/359168.359176.

38.

Shoup, Practical threshold signatures, in: Advances in Cryptology – EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Proceeding, Bruges, Belgium, May 14–18, 2000,

Preneel, ed., Lecture Notes in Computer Science, Vol. 1807, Springer, 2000, pp. 207–220. doi:10.1007/3-540-45539-6_15.

39.

N.P.

Smart and

Y.T.

Alaoui, Distributing any elliptic curve based protocol, in: Cryptography and Coding – 17th IMA International Conference, IMACC 2019, Proceedings,

Albrecht, ed., Oxford, UK, December 16–18, 2019Lecture Notes in Computer Science, Vol. 11929, Springer, Oxford, UK, 2019, pp. 342–366. doi:10.1007/978-3-030-35199-1_17.

40.

D.R.

Stinson and

Strobl, Provably secure distributed Schnorr signatures and a (t, n) threshold scheme for implicit certificates, in: Information Security and Privacy, 6th Australasian Conference, ACISP 2001, Proceedings, Sydney, Australia, July 11–13, 2001,

Varadharajan and

Mu, eds, Lecture Notes in Computer Science, Vol. 2119, Springer, 2001, pp. 417–434. doi:10.1007/3-540-47719-5_33.

41.

Wuille, BIP-32: Hierarchical Deterministic Wallets, https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki, accessed: 2020-11-15.

42.

A.C.

Yao, How to generate and exchange secrets (extended abstract), in: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986, IEEE Computer Society, 1986, pp. 162–167. doi:10.1109/SFCS.1986.25.

Fast threshold ECDSA with honest majority 1

Abstract

Keywords

1. Introduction

2 For this reason Bitcoin uses multisignatures [1]. But as discussed in length in e.g. Gennaro et al. [21] threshold signatures are in several ways more suited.

1.2. Concurrent work

3 http://keep.network

2.1. Signature schemes

2.2. The DSA/ECDSA standard

2.3. Shamir’s secret sharing

2.4. Joint random secret sharing

3. Our threshold ECDSA protocol

3.1. Technical overview

3.2. Computing powers of a point

3.3. Key generation

3.4. Signature generation

Theorem 3.1 (Informal).

4. Security analysis

4.1. The formal ideal functionality and protocol

6 We assume t corrupted parties. If less, the simulator can simply choose to corrupt additional parties in the simulation.

9 Note that a real broadcast is required here, since all honest parties need to agree that the pre-processing went well. Otherwise, we risk that a few honest parties may proceed to the online phase which will then abort, and so we no longer have guaranteed output delivery in the online phase.

Table 1 Concrete performance Protocol Bits sent per party Long exponentiations per party KEYGEN n log q + n log p 1 (and t 2 + t Lagrange exp) PRESIG 6 n log q + 2 n log p 3 (and 2 t 2 + 2 t Lagrange exp) SIGN n log q 2

References

²
For this reason Bitcoin uses multisignatures [1]. But as discussed in length in e.g. Gennaro et al. [21] threshold signatures are in several ways more suited.

³
http://keep.network

⁶
We assume t corrupted parties. If less, the simulator can simply choose to corrupt additional parties in the simulation.

⁹
Note that a real broadcast is required here, since all honest parties need to agree that the pre-processing went well. Otherwise, we risk that a few honest parties may proceed to the online phase which will then abort, and so we no longer have guaranteed output delivery in the online phase.

Table 1
Concrete performance

Protocol Bits sent per party Long exponentiations per party

$KEYGEN$ $n log q + n log p$ 1 (and $t^{2} + t$ Lagrange exp)

$PRESIG$ $6 n log q + 2 n log p$ 3 (and $2 t^{2} + 2 t$ Lagrange exp)

$SIGN$ $n log q$ 2