[Cryptography] Practical Threshold Signatures

[realcr]

Hi, I recently read the article "Threshold Signatures, Multisignatures and
Blind
Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme", written
by
Alexandra Boldyreva. Link can be found here:
https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf.  (Note: If you
are
going to read this, my question refers to the first parts of the article -
until
part 3 and including it.)

Does anyone here have any past experience with working implementations of
Threshold Signature mechanisms, or can point me somehow on the path to
implementing this the right way?

I will elaborate a bit about what I already know:

About Threshold Signatures:
---------------------------
There are n parties, and we want that k out of those n parties will have the
ability to sign in the name of the whole group of n parties. The naive
solution
could be to collect enough regular signatures from k participants, and the
concatenated result could serve us as a crude Threshold Signature.

A more advanced solution might be able to produce a final signature which
is of
smaller size, or even of the same size of a regular signature.

Very short summary of the first part of Alexandra's article:
------------------------------------------------------------
- There are some groups where the Gap Diffie Hellman property is assumed
(It is
    easy to solve the Decisional Diffie Hellman problem, but hard to solve
the
    Computational Diffie Hellman problem).

- Given that g is some (known to all parties) element of the group G, in
order
    to generate an identity to sign with, a party randomizes some x, and
defines y
    = g^x to be the public key.

- In order to sign a message m, the party calculates (H(m))^x, where H is a
hash
    function into G.

- A secret x could be shared (For example using Shamir secret sharing), and
    every party gets a private share of the secret. Thus party P_i for
example
    gets its share x_i of the secret.

- Because of the very simple structure of the signature, it is possible to
    combine signature shares of the form (H(m))^x_i together using lagrange
    interpolation to get the signature over the message m, which will
result in
    (H(m))^x.

My question about this scheme is as follows: Do you guys know any good GDH
(Gap
diffie hellman) groups that we can actually count on? I didn't manage to
find
anything myself. In addition, I notice that the signature proposed does not
involve any randomness in it. (It looks like ElGamal without the extra
part),
what do you think about it?

Modified ElGamal Alternative:
-----------------------------
If you managed to read so far, you must be interested enough to hear about
another alternative. I found the article "Group-oriented (t,n) threshold
signature scheme and digital multisignature" by L.Harn.

This article proposes some kind of modified ElGamal algorithm to be able to
do a
similar trick, in order to acheive threshold signatures. My problem here is
that
I'm not sure whether this modification is something that I can actually
trust,
and what is the right way to generate keys for this modified algorithm.

Victor Shoup's RSA Threshold Signatures:
----------------------------------------
I read a bit about Victor Shoup's idea for Threshold signatures in the
article
"Practical Threshold Signatures". I really liked it, though I can't put that
into use because it requires a trusted party to set up the secrets before
the
protocols begin. The other two options I discussed above have the following
very
attractive property: The secret is just a random number, not a pair of prime
numbers or any special number theoretical object. Thus it is far easier to
share
the secrets between the parties in the protocol in a distributed manner.

I am aware of some attempts in other articles to remove the trusted party
out of
the pre-setting of secrets in Victor Shoup's Threshold Signature, however it
seems to be very communication Expensive, much more than the actual
protocol I
want to run later. Thus I prefer not the use this schema, and I really want
to
make one of the former discussed schemas work.


If you happen to know about working code on this subject, or an idea about
implementing a nice one, please make sure to drop a message. I would
probably
like to participate if you are coding something of this type.

Regards,
real.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131112/943ec658/attachment.html>