Baird et al.'s unique threshold signature scheme


In this post, we describe a strawman threshold signature construction by Baird et al.1 which produces unique signatures. In their paper, Baird et al. modify this construction into a (non-unique) multiverse threshold signature scheme.


We assume familiarity with:

The idea

The Baird et al. strawman1 follows a very simple idea.

Each player $i\in[n]$ locally picks their secret key $\sk_i$ and computes their public key as $\pk_i = g^{\sk_i}$. Then, the SKs of a set of $n$ players can be used to define a degree-$(n-1)$ polynomial $f(X)$ as follows: \begin{align} f(i) &= \sk_i,\forall i \in[n] \end{align} To create a $t$-out-of-$n$ threshold signature scheme, the players can collaborate (in an MPC/DKG-like fashion), to publicly-reveal $n-t$ evaluations of this polynomials. This effectively reduces the degree of the polynomial to be $t-1$.

Open question: Can this protocol for publicly-revealing the $n-t$ evaluations can be instantiated any more efficiently than a DKG?

Specifically, the players use (some) DKG-like protocol to reveal: \begin{align} \mathsf{evals} = \left(f(-1), f(-2),\ldots,f(-(n-t))\right) \end{align} The secret key of the resulting $t$-out-of-$n$ threshold signature scheme is defined as: \begin{align} \sk = f(0) \end{align} The associated PK consists of the publicly-revealed evaluations and, of course, $g^{f(0)}$: \begin{align} \pk = (\mathsf{evals}, g^\sk) = \left(\mathsf{evals}, g^{f(0)}\right) = \left(\mathsf{evals}, \prod_{i\in[n]} \pk_i\right) \end{align} To assemble a threshold signature on a message $m$, each player $i$ reveals their signature share $H(m)^{\sk_i}$. Then, any aggregator who has $\pk$ and $t$ signature shares, can interpolate the unique threshold signature $H(m)^{f(0)}$ from (1) the signature shares and (2) the publicly-reveled evaluations in $\pk$.

We give more details below.

The construction

Below, we formally give the Baird et al. strawman1.

$\mathsf{Sig}$.$\mathsf{KeyGen}(1^\lambda) \rightarrow (\sk, \pk)$:

  • $\sk\randget\Zp$
  • $\pk \gets g^\sk$

$\mathsf{Sig}$.$\mathsf{DistKeyGen}(t, (\sk_i, \pk_i)_{i\in[n]}) \rightarrow (\sk, \pk)$:

  • Let $\ell_i = \prod_{j\in [n], j\ne i} \frac{0 - j}{i - j}$ be the Lagrange coefficients w.r.t. to $[n]$
  • Let $f(X) = \sum_{i\in[n]} \ell_i \sk_i$ be a polynomial such that $f(i) = \sk_i$
  • Let $\sk \gets f(0)$
  • Let $\pk \gets (g^\sk, f(-1), f(-2), \ldots, f(-(n-t))$

The $\mathsf{Sig.DistKeyGen}$ algorithm is run by the players in an MPC fashion such that it outputs the $\pk$ of the threshold signature scheme yet no one learns the $\sk$.

$\mathsf{Sig}$.$\mathsf{ShareSign}(\sk_i, m) \rightarrow \sigma_i$:

  • $\sigma_i \gets H(m)^{\sk_i}$

$\mathsf{Sig}$.$\mathsf{ShareVer}(\pk_i, m, \sigma_i) \rightarrow \{0,1\}$:

  • Return $e(\sigma_i, g) \equals e(H(m), \pk_i)$

$\mathsf{Sig}$.$\mathsf{Aggregate}(\pk, m, (\sigma_i)_{i\in T}) \rightarrow \sigma$:

  • Assert $|T| \ge t$ and $T \subseteq [n]$.
  • Let $P = \{-1, -2,\ldots, -(n-t)\}$ denote the publicly-revealed evaluation points in $\pk$
  • Let $\ell_i = \prod_{j\in P\cup T, j\ne i} \frac{0 - j}{i - j}$ be the Lagrange coefficients w.r.t. to $P\cup T$
  • Let $(\cdot, f(-1), f(-2), \ldots, f(-(n-t)) \gets \pk$
  • $\sigma \gets \prod_{i\in T} \sigma_i^{\ell_i} \prod_{i\in P} H(m)^{\ell_i f(i)}$

$\mathsf{Sig}$.$\mathsf{Verify}(\pk, m, \sigma) \rightarrow \{0,1\}$:

  • Return $e(\sigma, g) \equals e(H(m), \pk)$


This is a very nice scheme, but it has a few problems:

  1. It is unclear how to efficiently reveal the evaluations in $\mathsf{evals}$
  2. It is not secure in the multiverse setting (see how [BGJ+23]1 fixes it)

  1. Threshold Signatures in the Multiverse, by L. Baird and S. Garg and A. Jain and P. Mukherjee and R. Sinha and M. Wang and Y. Zhang, in 2023 IEEE Symposium on Security and Privacy (SP), 2023, [URL]  2 3 4