Derived keys usable by threshold signatures

Question

Suppose there are $n$ members in a $(t,n)$ threshold signature scheme. The global secret key $sk$ is not known to any single party, as the keys are generated distributed. The parties are able to construct their global public key $pk$. So each member $i$ can sign a message $m$ with their secret share $sk_{i}$ which will produce $sig_i$. All signatures shares can be combined to create $sig$ which is verifiable under $pk$.

Is there any key derivation function $f$, such that each member can produce derived keys $sk_i^1$,$sk_i^2$,$sk_i^3$,...$sk_i^n$, that will be able to fulfil the threshold scheme? E.g. every member signs $m'$ with $sk_i^1$ and the combined signature $sig^1$ is verifiable under $pk^1$ which is constructed from the shares $pk_i^1$.

Answer 1

There are two mainstream ways of doing this. Using Schnorr or BLS signatures. The Schnorr formulations are more complex, but if you are willing to use bilinear pairings, the BLS solution is straighforward to understand.

Assuming the existence of a set of Shamir's Secrets Shares $\{(x_i, y_i) \in \mathbb{F}^2_p: i \in [1, n] \cap \mathbb{Z}\}$, where the Lagrange interpolation $L(x) = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}(x)$ and $L(0) = y$ is the secret. Normally $x_i$ are public parameters and simplified to $x_i = i$.

Defining the bilinear pairing as $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{F}^{*}_{p^{k}}$, in type-3 settings, and a hash-to-curve $H: \{0,1\}^* \mapsto \mathbb{G}_2$.

Also $y \times G \mapsto Y$ is the corresponding public key, with $G,Y \in \mathbb{G}_1 $.

The BLS signature is defined as:

$Sign(y, m) \mapsto \mathbb{G}_2$ with the output $y \times H(m) \mapsto S$

And verified with:

$Verif(Y, m) \mapsto \{0,1\}$, result in 1 if $e(Y, H(m)) = e(G, S)$

To transform this in a threshold scheme just apply the Lagrange interpolation directly:

$S = y \times H(m) = \sum_{i=1}^{t+1} y_{i} \cdot l_{i}(x) \times H(m)$

From a client, you can collect $t+1$ partial signatures $y_{i} \times H(m)$ and interpolate to construct $S$. Verification is unchanged.

However, this simple procedure cannot prevent parties from sending wrong results $y^{'}_i \times H(m^{'})$. It can result in a valid signature for an unkwon message. Although this is not a big concern for most practical purposes, it's something you should be aware.