Notes on threshold signature schemes

A threshold signature allows a subset t of a group of n possible signers to collectively produce a signature for the entire group. The simplest ones tend to use some distributed key generation ("DKG") based on verifiable secret sharing ("VSS") to construct the keys and secret inputs to a Schnorr signature in a distributed manner. There have been a lot of these, and recalling all the Feldman-this and Pedersen-that gets confusing. The following seem to be the core papers in the field of discrete-log threshold signatures:

  • Pedersen DKG (1991) was the first threshold scheme. It uses an earlier primitive called Feldman VSS. It was later found to be vulnerable to malicious participants, but nevertheless remains a building block of subsequent schemes.
  • GJKR DKG (1999) describes the attack against the Pedersen DKG, which can be manipulated by participants to produce non-uniform keys. Their fix adds a new commitment round (which uses the alternative Pedersen VSS) to eliminate the ability of a participant to bias the results.
  • GJKR Revisited (2003) describes a threshold Schnorr scheme that is secure even when using the original Pedersen DKG. The signature scheme isn't necessarily great, but it does save a round of communication vs GJKR99. Their main innovation is actually the proof techniques that explain when the problem with Pedersen DKG does not affect the security of the signature.
  • Stinson-Strobl (2001) is kind of off on its own, applying the GJKR99 result directly. It is more commonly cited now but GJKR03 appear to have been unaware of it.
  • This is some sort of helpful extended version of the GJKR work, combining GJKR99 and GJKR03 with good explanations of the design motivations. I have no idea what the context of this version was.