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.
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography