Threshold ECDSA protocols

Threshold ECDSA protocols #

In this series of posts, we will review some of the most relevant works on threshold ECDSA protocols. We present a summary of each work, and after an analysis of the protocols, we include some “security concerns”, which are points of the protocol to which the auditors and developers need to pay special attention during the revision of an implementation. Those security concerns are extracted from each paper itself, which means that the list does not cover all the possible implementation issues that may arise. Also, for some protocols, we corrected some typos present in the papers to help developers avoid confusion and errors during the implementation process. Finally, we also present some repositories and libraries that implement different threshold ECDSA protocols.

Intuitively, a threshold signature scheme is a cryptographic functionality that allows a set of $n$ parties to somehow distribute a signing key among them in such a way that only a subset of more than or equal to $t$ parties can sign a message but a subset of less than $t$ parties can do nothing. Such cryptographic primitive has been used actively for key protection in blockchain applications to avoid private key theft and secure financial assets. In this document, we present a summary of some $(t, n)$ signature schemes for the case of $(2, 2)$, $(2, n)$, and the more general case $(t, n)$. This document will contain three main elements of interest: a protocol description for each scheme considered in this work, a list of libraries that implement the protocols, and some security concerns that should be considered at the moment of implementing these protocols.

The standalone ECDSA signature scheme #

In order to fully understand the threshold ECDSA protocols, we will revisit first the basics of the ECDSA signature scheme without considering multiple parties, just the standalone cryptographic scheme. First, we need to know that the security of the ECDSA signature scheme relies on the discrete logarithm problem. To explain such problem at a high level, let $\mathbb{G}$ be a cyclic group with order $q$ and let $G$ be a generator for the group. The discrete logarithm problem relative to $\mathbb{G}$ and $G$ consist in that, given a random element $R = x \cdot G$, to find $x \in \mathbb{Z}_q$ such that it fulfills the equality. In the literature, the discrete logarithm assumption is that there is a polynomial-time algorithm that generates a group $\mathbb{G}$ with its order $q$ and generator $G$ such that the discrete logarithm problem is computationally hard. In practice, ECDSA signature schemes use the group of points generated by an elliptic curve.

Now, let $H: \\{0, 1\\}^* \rightarrow \mathbb{Z}_q$ be a hash function (in practice, SHA256 is used). In what follows, let $\mathbb{G}$ be an elliptic curve group of order $q$ with generator $G$. Let us describe the algorithms for key generation, signing, and verification for the ECDSA signature scheme:

  • $\textsf{Gen}$: the key generation algorithm works as follows:

    1. Sample a random element $x \in \mathbb{Z}_q$.
    2. Compute $X = x \cdot G$.
    3. Output $x$ as the secret key and $X$ as the public key.

  • $\textsf{Sign}$: on input $m \in \\{0, 1\\}^*$ as the message to be signed, and the private key $x \in \mathbb{Z}_q$,

    1. Compute $m'$ as the $|q|$ leftmost bits of $H(m)$, where $|q|$ is the bit-length of $q$.
    2. Choose a random element $k \in \mathbb{Z}_q^*$.
    3. Compute $R = k \cdot G$ and let $R = (r_x, r_y)$. Remember that $R$ is a point over an elliptic curve whose representation is in the cartesian plane. Therefore each point can be represented as a pair.
    4. $r = r_x \mod q$. If $r = 0$ the process returns to Step 2 to select a fresh random $k \in \mathbb{Z}_q^*$.
    5. Compute $s = k^{-1} \cdot (m' + r \cdot x) \mod q$.
    6. Output the pair $(r, s)$ as the signature.

    It is important to highlight that if $(r, s)$ is a valid signature for a message $m$, then $(r, -s)$ is also a valid signature for this message. Therefore, it is common to choose $\min\\{s, -s\\}$ in $\mathbb{Z}_q$ to obtain a unique signature.

  • $\textsf{Verify}$: On input $(r, s)$ to be the signature and $m \in \\{0, 1\\}^*$ to be the signed message,

    1. Compute $m'$ as the $|q|$ leftmost bits of $H(m)$.
    2. Compute $s^{-1}\left(m' \cdot G + r \cdot X\right)$ and accept if the first component is equal to $r$.

Notice that extracting the first component of a point on the elliptic curve is commonly used here. That can be represented as a function $F: \mathbb{G} \rightarrow \mathbb{Z}_q$, and in the case of ECDSA, it can be defined as $F(x, y) = x \mod q$. It is important to highlight that when we consider a generic abstract cyclic group, a generic function $H: \\{0, 1\\}^* \rightarrow \mathbb{Z}_q$, and a generic function $F: \mathbb{G} \rightarrow \mathbb{Z}_q$, assuming that the discrete logarithm problem and modeling $H$ and $F$ as random oracles, one can prove that such abstract version of the signature scheme is secure. When the ECDSA is instantiated as described in the algorithms $(\textsf{Gen}, \textsf{Sign}, \textsf{Verify})$, is reasonable to model $H$ as a random oracle, but modeling $F$ as a random oracle in this case is not a correct model because $F$ is far from behave as a random function. Despite this, ECDSA has been used and studied and the scrutiny process so far has revealed no significant attack.

Standalone ECDSA security concerns #

  • Bad generation and manipulation of $k \in \mathbb{Z}_q^*$ in DSA/ECDSA can lead to catastrophic results (see Katz & Lindell, 2014, Section 12.5.2). If the attacker can predict the value of $k$, or if the same $k$ is used twice in two different signature generations, the attacker can obtain the secret key (the latter can occur even if $k$ is unpredictable). The later attack was used to extract the master key on PS3.
  • Let $m \in \\{0, 1\\}^*$ the message to be signed. Before the process starts, we should compute $m'$ to be the $\vert q \vert$ leftmost bits of $\textsf{SHA256}(m)$, where $\vert q \vert$ is the bit-length of $q$. This is in fact the message that should be signed, and not $m$ itself (see Lindell, 2021).

Libraries for computing threshold ECDSA #

References #

  • Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography, Second Edition. Chapman & Hall/CRC.
  • Lindell, Y. (2021). Fast Secure Two-Party ECDSA Signing. Journal of Cryptology, 34(4), 44. doi:10.1007/s00145-021-09409-9.