Technical Report on Threshold ECDSA in the Preprocessing Setup

Threshold ECDSA (Elliptic Curve Digital Signature Algorithm) has garnered significant attention from both industry and research, primarily due to its blockchain applications, especially in the context of threshold wallets. Existing solutions often assume that the client is either an integral part of the signers, as evident in self-custodial or non-custodial wallets, or that they entirely delegate the signing procedure to an external network, as observed in custodial wallets. The former allows clients to defend against collusion attacks from other signers, while the latter enables more efficient online phases through the use of preprocessing material. In this report, we explore the development of a threshold signature scheme that keeps some of the key benefits from both custodial and non-custodial settings. Specifically, we present a threshold ECDSA signature scheme in the client-server model that combines the optimal online round complexity from the custodial setting with resilience against collusion among all signer nodes during the online phase, as observed in non-custodial wallets. The scheme is also secure against user impersonation attacks, a key concern with custodial wallets. 1 Introduction Threshold cryptography distributes information and responsibility among multiple parties [5, 12, 25], enhancing security and resilience. A prominent application of this approach is threshold signature schemes (TSS), where a set of n parties possessing shares of the signing key can sign a message M only if at least t parties agree to sign [11]. By decentralizing the signing process through a network of diverse entities, this strategy mitigates the risk of single points of failure. Recently, (TSS) have been adopted within the Web3 ecosystem [19, 9] as a measure to enhance security and mitigate inherent risks associated with client-driven key management. Precisely, TSS schemes allow wallets to operate within three distinct scenarios: custodial, wherein all signing key shares are distributed among a designated set of signing parties; self-custodial, whereby the client exclusively manages all cryptographic keys; and non-custodial, involving the distribution of signing key shares between the client and designated signing parties [9]. Custodial wallets present operational advantages over non-custodial counterparts: they delegate key management responsibilities to external service providers staffed by security experts, thereby reducing the risk of theft or loss. Additionally, from an efficiency standpoint, custodial wallets do not necessitate client involvement in the signing process, allowing preprocessing tasks to be efficiently handled by the network before signing. However, custodial wallets exhibit vulnerability to full collusion among signers, whether for signing new messages or disclosing shared secret keys. This vulnerability is addressed by non-custodial wallets, where the client actively participates in the signing process. Moreover, entrusting key management responsibilities in custodial setups 1 introduces the risk of user impersonation attacks, wherein an attacker seizes control of the user’s wallet by posing as the legitimate user. Consequently, there exists a desire to combine the benefits of both custodial and non-custodial solutions. While TSS protocols maintain transparency regarding the roles of clients and signing parties, enabling execution in both custodial and non-custodial settings, they lack the flexibility for threshold wallets to optimize advantages from both approaches. Therefore, one might wonder: Is it possible to develop a TSS protocol that keeps some of the key benefits of both custodial and non-custodial settings? In this report, we present a threshold ECDSA signature scheme in the client-server model [21] that keeps the operational benefits of a custodial setting while eliminating impersonation attacks and approximating its trust assumptions to the unforgeability robustness of the non-custodial setting. This is realized through the encryption of precomputed material linked to the secret key and a white-box application of a secure multiparty computation (MPC) protocol [27], recently introduced and instantiated using additive shares. Related work. Some signature schemes, such as BLS and Schnorr’s scheme, can be easily adapted to the threshold setting [4]. However, the elliptic curve digital signature algorithm (ECDSA) has received more research attention due to the challenges of executing non-linear operations over shares. Recent papers [20, 15, 14, 6, 8, 13] mainly focus on dishonest majority scenarios with statically corrupted parties, which is suitable enough for practical deployment as highlighted in [1]. Nonetheless, these approaches often rely on additional assumptions, such as strong RSA [14, 6] and utilize complex building blocks such as Multiplicative-to-Additive (MtA) shares [14, 6, 13]. These factors increase the complexity of deployments, thereby making them vulnerable to potential attacks [2, 26, 24]. Optimization efforts primarily target reducing communication rounds in TSS protocols, which heavily rely on network latency [1]. The most efficient protocols, such as [6, 8], operate in a preprocessing setup, where a presignature is generated, enabling a non-interactive online phase. However, these protocols do not address a scenario where the client does not own a share of the signing key while having the ability to prevent signers from signing independently under full collusion. Our contribution. We introduce a threshold ECDSA scheme in the dishonest majority setting with abort within the client-server model, creating sufficient preprocessing material to facilitate an optimal online phase — comprising one round for the client to transmit a message to the servers and another round to receive the result. Our protocol is unforgeable with n − 1 corruptions and with full collusion among signers during the client dependent phase of the distributed signing protocol. Furthermore, it is secure against user impersonation attacks. High-level picture of the scheme. The proposed scheme is tailored for deployment in a network architecture where individual clients are connected with a group of n signers. In essence, the network holds encrypted shares related to the signing secret key, while the clients possess the secret key of the corresponding encryption scheme. This configuration empowers the client to prevent unauthorized attempts by the signers to forge signatures. We follow the MPC protocol outlined in [27]. This protocol calculates multivariate polynomials without interaction during the computation phase. Specifically, the protocol operates on elements of the form ⟨x⟩λ := x · h−λ where λ is secret shared between the parties. Within the context of 2 this report, we refer to ⟨x⟩λ as a masked value of x with respect to the masking exponent λ using public generator h. It is worth noting that this construction essentially constitutes a multiplicative one-time pad in the multiplicative group Z∗ q, for prime q. The signature scheme comprises two protocols: a distributed key generation (DKG) protocol, denoted as πDKG, and a threshold signing protocol, denoted as πSign. To ensure compatibility with the underlying MPC protocol [27], the DKG protocol outputs an encrypted signing secret key share tuple (⟨x⟩λ,epk,λ) alongside the conventional signing public key y = x · G, where G represents an elliptic curve generator. Here, epk,λ := Encpk(λ), with · denoting the additive secret sharing scheme in Zq−1 and Encpk representing an additively homomorphic scheme under the public key pk and secret key sk owned by the client. The generation of the random masked value ⟨x⟩λ and the corresponding public key y is accomplished using standard MPC primitives combined with preprocessing material from the MPC protocol [27]. This involves the reconstruction of additive shares both in the exponent of h ∈ Z∗ q and in the coefficient of a chosen elliptic curve generator G. The threshold signing protocol, denoted as πSign, is designed to compute the ECDSA signature equation. This equation takes the form of a polynomial (s = k−1·m+k−1·x·r), where all elements are in the field Zq. The signing protocol is structured into three distinct phases:

1. Signers preprocessing phase: This phase involves computing preprocessing material without requiring any client intervention. An interesting optimization in this phase is the local computation of inversions, utilizing the property ⟨x⟩−1 λ =⟨x−1⟩−λ. This phase assumes at least one signer is honest.

2. Client preprocessing phase: This phase consists of a single round where signers reveal two masking exponents to the client. This phase tolerates full signer corruption.

3. Online phase: This phase encompasses two rounds. In the first round, the client sends the message to be signed, and in the second round, the client receives the result from the signers. It is noteworthy that during the online phase, no communication occurs among the signers, resembling the evaluation phase of the MPC protocol as detailed in [27, Section 2.2]. This phase also tolerates full signer corruption. 2 Technical overview 2.1 ECDSA Signing We recall that ECDSA is parametrized by an elliptic curve over a finite field and defined by a triple (G,G,q), where G is an additive subgroup of points in the curve with prime order q and generator G. Given message M, secret key x and random nonce k in Z∗ q, the ECDSA signature is a pair (s, r) ∈ Z∗ q where s = k−1 · (H(M) +x·r), for a cryptographic hash function H. Here, r is the x-coordinate of the point k · G, i.e. (r, ) := k · G. 2.2 Secret sharing A (t,n)−threshold secret sharing scheme is a pair of algorithms (Share,Reconstruct). The Share algorithm splits a secret value into n shares and the Reconstruct algorithm recovers the initial secret value with only t +1 shares. We employ in our threshold signature construction the additive secret sharing scheme. In this scheme, a number x ∈ Zq is shared among n parties Pi by sending random xi ∈ Zq to Pi such that x = n i xi mod q. The reconstruction is achieved by having all parties send their share xi to each 3 other. Throughout this report, we denote by [x] := {[x]1,...,[x]n} additive shares in Zq and x additive shares in Zq−1. 2.3 Additively Homomorphic Encryption Our protocol uses an encryption scheme with the following two homomorphic properties: • Apair of encrypted ciphertexts can be added. • An encrypted ciphertext can be multiplied by a plaintext. Informally, an additively homorphic encryption sheme consists of three algorithms E =(KeyGen,Encpk,Decsk), where KeyGen generates the public and private key pair (sk,pk) and Encpk and Decpk are the encryption and decryption algorithms, respectively. The first homomorphic property guarantees that there exists an efficient operation ⊞ such that a + b = Decsk(Encpk(a) ⊞ Encpk(b)), the second that there exists an efficient operation such that a · b = Decsk(Encpk(a) b). Standard examples of such encryption schemes include those of Paillier [22] and Castagnos-Laguillaumie [7]. 2.4 The Underlying MPC Protocol We make use of the MPC protocol introduced in [27] instantiated with an additive secret share scheme to obtain a non-interactive online phase. The work [27] also introduces the concept of masked factors as follows. A masked factor ⟨x⟩λ hiding a non-zero secret x ∈ Z∗ q with independent uniformly random mask exponent λ ∈ Zq−1 is given as ⟨x⟩λ = x·h−λ ∈ Z∗ q, where h is a public generator in Z∗ q. We refer to the element h−λ as the multiplicative mask. To simplify notation, we often use ⟨x⟩ when λ is implicit. Observe that, in the description of our protocol below, we often include in the random mask exponent, λx, its corresponding secret variable label, x. For readability purposes, we might use one or the other. Protocol. For a description of the protocol we refer to [27, Section 2]. It aims at evaluating a multivariate polynomial of the form: A z = a=1 Ma m=1 xa,m, where xa,m are secrets owned by input parties, a stands for the terms being added and m for the factors being multiplied in one term. The protocol is divided in two phases: a preprocessing phase, (FPREPROC, [27, Figure 1]), that generates shares {[hγa]},{λa,m} such that Ma γa = m=1 λa,m, (1) and a computation phase (π, [27, Figure 2]), that generates the masked factors with λa,m as mask exponents, i.e. ⟨xa,m⟩λa,m and that computes the polynomial in secret shared form using the expression: A [z] = a=1 M [hγa] m=1 ⟨xa,m⟩λa,m