To Home page

Threshold Signatures

This is not in fact a useful discussion of Threshold signatures, so much as a list of not very useful links. I don't actually understand how to implement threshold signatures, nor what the scaling laws are for the solution in the case of many signatures and possible byzantine generals behavior.

The first threshold signatures that do not require a trusted dealer appear to be:

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

Genarro's method is briefly described by Wikipedia as follows:

The distributed key generation protocol specified by Gennaro, Jarecki, Krawczyk, and Rabin assumes that a group of players has already been established by an honest party prior to the key generation. It also assumes the communication between parties is synchronous.

1. All parties use Pedersen's verifiable secret sharing protocol to share the results of two random polynomial functions.

2. Every party then verifies all the shares they received. If verification fails, the recipient broadcasts a complaint for the party whose share failed. Each accused party then broadcasts their shares.

3. Each party then has the opportunity to verify the broadcast shares or disqualify accused parties. All parties generate a common list of non-disqualified parties.

4. Each non-disqualified party broadcasts a set of values constructed by raising a common generator to the power of each value used in one polynomial in Part 1.

5. These broadcast values are verified by each party similarly to as in Part 2. When a verification fails, the party now broadcasts both the values received in Part 1 and the values received in Part 3. For each party with verifiable complaints, all other parties reconstruct their own value sets in order to eliminate disqualified contributions.

The group computes the private key as the product of every qualified contribution (each qualified party's random polynomial evaluated at 0

But this method is of order n2 for each participant so is unworkable for interesting numbers of shares.

A method that is actually practical is: Possibly Practical Large Scale Distributed Key Generation which is order [log (n)]3.

Bouncy castle has code for this purpose. I don't know if it is fit for my case.

See my discussion of pairing based cryptography

The threshold variant of the scheme described in pairing based cryptography is called GDH threshold signature scheme. (Gap Diffie Hellman Threshold Signature Scheme)

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