The Standard Threshold Signature Scheme
Tags: blockchain, web3
Published: 2022-07-26 09:44:00

We continue publishing articles on the principles of the threshold signature scheme. Previously we talked about the [standard digital signature scheme (DSS)](https://dev.to/symbiosis_fi/introduction-to-threshold-signatures-18co), covered the main ideas behind the elliptic curve theory and provided a brief overview of the [ECDSA algorithm](https://dev.to/symbiosis_fi/ecdsa-algorithm-1lh7). 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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4e7ix0gptu33gl5601zd.png)

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:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/u78ndxzqkwzgerf0q5xn.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ey7ha9olzz4xv6vq8kx9.png)

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


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w843t4gpx4t8frddk4vg.png)

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”](https://eprint.iacr.org/2019/114.pdf)


**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.**