Threshold Signatures

The most advanced threshold signatures appear to be:

Efficient threshold signature, multisignature, and blind signature schmes based on the Gap-Diffie-Hellman-Group signature scheme

By Alexandra Boldreva

Published in Public Key Cryptography (PKC) 2003, LNCS 2567, Springer-Verlag, Berlin 2003

page 31

Builds on, and requires understanding of, Boneh, Lynn, And Sacham [8] "groups where the Computational Diffie-Hellman (CDH) is hard, but the Decisional Diffie-Hellman (DDH) problem is easy."

For background on such groups, she cites 6,8, 29, 30, which cites I have not yet dug up, due to google limits.

CDH is to compute h=g^(log(u).log(v)) for random g,u, v, logs to base g

DDH is to decide whether (g, u, v, h) are a valid Diffie-Helmman tuple, meaning that they have the property that log u to the base g = log h to the base v, in other words, whether there exists X: u=g^X and h=v^X

In Gap Diffie Helman groups (GDH groups, we can solve DDH, but not CDH

This makes signing easy: g is widely known, Bob's private key is b, his public key is B=g^b

To sign a document, use a hash of the document to construct a random member of the group h. To sign the random member of the group, calculate H=h^b

To verify a signature, test whether (g, B, h, H) is a valid Diffie-Helmman tuple. So the test requires B, H, and the document, g being constant, and h calculable.

The threshold variant of this scheme is called GDH threshold signature scheme.

No trusted dealer is required, which is to say the scheme actually works, or at least is not yet known to be broken. RSA requires a trusted dealer to create the keys, which trusted dealer is supposed to forget the keys, (pigs will fly)

This scheme is also good for blind signatures.

I have read google's report on this up to page 35, switching countries to US, due to viewing limit

On page 37, gives a formal description of the ordinary signature scheme, which has already been described informally.

Then starts describing "Robust Proactive Threshold GDH Signature Scheme"

Threshold Key generation is the protocol of Gennaro [22]. Everyone gets a private key and a public key, and a protocol to generate the group public key from a subset of private keys. I can see where this is going. Due to the special properties of our group, the protocol to generate the group public key can generate the group signature instead. "Using the well known techniques of Lagrange interpolation"

A subset of players make public each one's signature of a quantity, and the group signature can be constructed (by anyone and everyone) from a sufficient number of these individual signatures - following the somewhat vaguely described method of Gennaro [22]. (To prevent disruption, each individual signature must be checked for validity.)

The magic formula here is that "using the well known techniques of Langrange interpolation" we can construct a group signature from a threshold number of individual signatures in a time that is linear in group size.

These documents are licensed under the Creative Commons Attribution-Share Alike 3.0 License