1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The key generation and distribution vs threshold signatures are two different problems. What do you want to solve exactly? $\endgroup$ – shumy Jan 29 at 15:31
  • $\begingroup$ I want to know if they can be used together. $\endgroup$ – Strernd Jan 29 at 16:20
  • $\begingroup$ Yes, however, constructing a threshold signature is more complex than just interpolating all the $sig_{i}$ results. $\endgroup$ – shumy Jan 29 at 16:36
  • $\begingroup$ 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. $\endgroup$ – Strernd Jan 30 at 9:19
  • 1
    $\begingroup$ 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 $\endgroup$ – lovesh Jan 30 at 12:24
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks four your answer, but I can't see how this comes together with derivated keys? $\endgroup$ – Strernd Jan 30 at 16:42
  • $\begingroup$ $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. $\endgroup$ – shumy Jan 30 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.