<div dir="ltr">Hi, I recently read the article "Threshold Signatures, Multisignatures and Blind<br>Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme", written by<br>Alexandra Boldyreva. Link can be found here:<br>
<a href="https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf">https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf</a>.  (Note: If you are<br>going to read this, my question refers to the first parts of the article - until<br>
part 3 and including it.)<br><br>Does anyone here have any past experience with working implementations of<br>Threshold Signature mechanisms, or can point me somehow on the path to<br>implementing this the right way?<br><br>
I will elaborate a bit about what I already know:<br><br>About Threshold Signatures:<br>---------------------------<br>There are n parties, and we want that k out of those n parties will have the<br>ability to sign in the name of the whole group of n parties. The naive solution<br>
could be to collect enough regular signatures from k participants, and the<br>concatenated result could serve us as a crude Threshold Signature. <br><br>A more advanced solution might be able to produce a final signature which is of<br>
smaller size, or even of the same size of a regular signature.<br><br>Very short summary of the first part of Alexandra's article:<br>------------------------------------------------------------<br>- There are some groups where the Gap Diffie Hellman property is assumed (It is<br>
    easy to solve the Decisional Diffie Hellman problem, but hard to solve the<br>    Computational Diffie Hellman problem).<br><br>- Given that g is some (known to all parties) element of the group G, in order<br>    to generate an identity to sign with, a party randomizes some x, and defines y<br>
    = g^x to be the public key.<br><br>- In order to sign a message m, the party calculates (H(m))^x, where H is a hash<br>    function into G.<br><br>- A secret x could be shared (For example using Shamir secret sharing), and<br>
    every party gets a private share of the secret. Thus party P_i for example<br>    gets its share x_i of the secret. <br>    <br>- Because of the very simple structure of the signature, it is possible to<br>    combine signature shares of the form (H(m))^x_i together using lagrange<br>
    interpolation to get the signature over the message m, which will result in<br>    (H(m))^x.<br><br>My question about this scheme is as follows: Do you guys know any good GDH (Gap<br>diffie hellman) groups that we can actually count on? I didn't manage to find<br>
anything myself. In addition, I notice that the signature proposed does not<br>involve any randomness in it. (It looks like ElGamal without the extra part),<br>what do you think about it?<br><br>Modified ElGamal Alternative:<br>
-----------------------------<br>If you managed to read so far, you must be interested enough to hear about<br>another alternative. I found the article "Group-oriented (t,n) threshold<br>signature scheme and digital multisignature" by L.Harn. <br>
<br>This article proposes some kind of modified ElGamal algorithm to be able to do a<br>similar trick, in order to acheive threshold signatures. My problem here is that<br>I'm not sure whether this modification is something that I can actually trust,<br>
and what is the right way to generate keys for this modified algorithm.<br><br>Victor Shoup's RSA Threshold Signatures:<br>----------------------------------------<br>I read a bit about Victor Shoup's idea for Threshold signatures in the article<br>
"Practical Threshold Signatures". I really liked it, though I can't put that<br>into use because it requires a trusted party to set up the secrets before the<br>protocols begin. The other two options I discussed above have the following very<br>
attractive property: The secret is just a random number, not a pair of prime<br>numbers or any special number theoretical object. Thus it is far easier to share<br>the secrets between the parties in the protocol in a distributed manner.<br>
<br>I am aware of some attempts in other articles to remove the trusted party out of<br>the pre-setting of secrets in Victor Shoup's Threshold Signature, however it<br>seems to be very communication Expensive, much more than the actual protocol I<br>
want to run later. Thus I prefer not the use this schema, and I really want to<br>make one of the former discussed schemas work.<br><br><br>If you happen to know about working code on this subject, or an idea about<br>implementing a nice one, please make sure to drop a message. I would probably<br>
like to participate if you are coding something of this type.<br><br>Regards,<br>real.<br><br></div>