# Derived keys usable by threshold signatures

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

• The key generation and distribution vs threshold signatures are two different problems. What do you want to solve exactly? Jan 29, 2020 at 15:31
• I want to know if they can be used together. Jan 29, 2020 at 16:20
• Yes, however, constructing a threshold signature is more complex than just interpolating all the $sig_{i}$ results. Jan 29, 2020 at 16:36
• Yes, that's why the question is, if there is a KDF, whose key derivates can be used for a threshold signature without additional constructions. Jan 30, 2020 at 9:19
• There is a somewhat related work called Pixel (eprint.iacr.org/2019/514.pdf) where you can do forward secure multi-signatures or threshold signatures (using similar ideas as for BLS sigs). However, to create a (multi or threshold)signature, all parties have to use the key at the same index in the derivation chain Jan 30, 2020 at 12:24

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.

• Thanks four your answer, but I can't see how this comes together with derivated keys? Jan 30, 2020 at 16:42
• $y_i$ are the derived keys $sk_i$. You can construct them using "Homomorphic secret sharing" where each party uses a polinomial with a secret. I was assuming you had knowledge about the procedure. Jan 30, 2020 at 18:08