We continue publishing articles on the principles of the threshold signature scheme. Previously we talked about the standard digital signature scheme (DSS), covered the main ideas behind the elliptic curve theory and provided a brief overview of the ECDSA algorithm. In this article we will introduce the concept of a threshold signature.
Earlier, we discussed DSS and its most common implementation ECDSA: tools that allow us to create individual signatures. Now let’s figure out how a group of users can create signatures jointly. This problem is particularly relevant since this type of joint signatures offers the highest level of security, which is especially crucial in DeFi.
In general terms, the problem is stated as follows. There are N parties who want to establish a system where any t of them are able to jointly create signatures on behalf of the entire group, whereas any subset of fewer parties is not able to do so. The number t, in this case, is called a threshold, and the resulting signature is called a threshold one.
As we know, a secret key is what determines a signature. That’s why the problem of creating a threshold signature comes down to the concept of a threshold secret sharing of a secret key. Namely, the secret key is divided into N parts, which are also called shares. Each party gets their own share and knows nothing about the other ones. Any t shares are enough to generate a joint signature on their basis. But any smaller amount of shares does not allow this to be done.
The crucial underlying property of such secret sharing is that any t shares are enough to simply derive the original key. But clearly, it’s also its biggest weakness. Because a party who discovers at least t-1 other shares will be able to extract the original key and subsequently create signatures on behalf of the entire group using the standard Sig algorithm from DSS. This is something undesirable; since, commonly, parties don’t trust each other. So it’s essential for them to keep their shares secret.
As for the public key, there’s no need for any particular approach. Public keys are used to verify signatures. And it doesn’t matter to those who verify whether a signature is individual or threshold one.
Thus, the Standard Threshold Signature Scheme (TSS) is a set of two protocols ThreshKeyGen and ThreshSig. These are step-by-step instructions that allow parties to create a pair of keys in the first case and a threshold signature in the second. Since a public key and a signature produced by these protocols have the usual format, there’s no need for a specific verifying algorithm. That is any threshold signature can be verified using the standard Ver algorithm from DSS.
The Threshold ECDSA protocol
Threshold ECDSA is a particular implementation of TSS, based on the ECDSA algorithm. So, just like ECDSA, this threshold version assumes a pre-generation of five domain parameters: a particular elliptic curve, a prime number n, a point G on the curve such that n is the order of G, and two other parameters related to modular arithmetic.
Key generation with ThreshKeyGen protocol
As a result of this protocol, each party receives a unique secret share skᵢ of the secret key sk and a copy of the same public key pk. Together the shares
constitute a (t, N) — threshold secret sharing of sk. That is, it is possible to derive the original key from any t these shares, but not from any smaller number of them.
At first, each party chooses a random number uᵢ. The secret key sk is defined as a formal sum of these values:
We use the word ‘formal’ because nobody knows all the numbers uᵢ, and so nobody can actually calculate this sum.
As in the standard KeyGen algorithm from ECDSA, the public key pk is defined by the formula pk=sk ∙ G. Only now it is calculated by parts. Each party finds their own point Qᵢ=uᵢ ∙ G on the curve for their own value of uᵢ. Then parties send their points to each other. Having all the points
each party calculates pk using a special rule for elliptic curve points that we haven’t yet covered.
It may seem that everything’s done. However, the parts
of the key sk aren’t superb. They do not have the desired threshold property: it’s impossible to derive the original key from any t of them because to do so you clearly have to know them all. Numbers uᵢ were just the necessary first step. They were needed to define the secret key sk. And now sk should be re-shared in a threshold way.
To make it happen, the parties use the additional protocol Feldman’s VSS (Feldman’s Verifiable Secret Sharing). This protocol consists of three steps:
First, each party performs a (t, N) — threshold secret sharing of their value uᵢ. Namely, uᵢ is divided into N parts so that it can be restored from any t of them, but not from a smaller amount.
Next, each party keeps one share of uᵢ and sends the other N-1 to the rest of the group: one share to each.
Finally, the parties check whether the shares they received are correct.
After these three steps each party will have N numbers. One was originally obtained during the first step. The rest N — 1 were received during the second step. Then each party obtains the final share skᵢ of the secret key sk as the sum of these N numbers.
Signature generation with ThreshSig protocol
The protocol ThreshSig assumes the participation of only t parties instead of N, since t parties are enough to generate a threshold signature successfully.
ThreshSig is a modified version of the standard _Sig _algorithm from ECDSA. The main difference is that now the signature is not calculated directly, but by parts.
Each party obtains a piece of the final signature using the unique share skᵢ of the secret key sk. Then these pieces are put together and the final signature (r, s) is calculated as their sum.
References
Rosario Gennaro, Steven Goldfeder, “Fast Multiparty Threshold ECDSA with Fast Trustless Setup”
In our first three articles we introduced some of the main algorithms related to digital signatures. Now we are going to delve into these algorithms and analyze them using the proper mathematical tools. In our next article we will have a brief excursion into group theory.
Top comments (0)