[148142] in cryptography@c2.net mail archive
[Cryptography] Practical Threshold Signatures
daemon@ATHENA.MIT.EDU (realcr)
Tue Nov 12 15:35:13 2013
X-Original-To: cryptography@metzdowd.com
Date: Tue, 12 Nov 2013 19:33:49 +0200
From: realcr <realcr@gmail.com>
To: cryptography@metzdowd.com, cryptography@randombit.net
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============1918693476352794510==
Content-Type: multipart/alternative; boundary=001a11c24b0a69c68204eafe40f8
--001a11c24b0a69c68204eafe40f8
Content-Type: text/plain; charset=ISO-8859-1
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.
--001a11c24b0a69c68204eafe40f8
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hi, I recently read the article "Threshold Signatures=
, Multisignatures and Blind<br>Signatures Based on the Gap-Diffie-Hellman-G=
roup Signature Scheme", written by<br>Alexandra Boldyreva. Link can be=
found here:<br>
<a href=3D"https://www.iacr.org/archive/pkc2003/25670031/25670031.pdf">http=
s://www.iacr.org/archive/pkc2003/25670031/25670031.pdf</a>.=A0 (Note: If yo=
u are<br>going to read this, my question refers to the first parts of the a=
rticle - 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 p=
oint 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 Si=
gnatures:<br>---------------------------<br>There are n parties, and we wan=
t that k out of those n parties will have the<br>ability to sign in the nam=
e 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 whic=
h 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>
=A0=A0 =A0easy to solve the Decisional Diffie Hellman problem, but hard to =
solve the<br>=A0=A0 =A0Computational Diffie Hellman problem).<br><br>- Give=
n that g is some (known to all parties) element of the group G, in order<br=
>=A0=A0 =A0to generate an identity to sign with, a party randomizes some x,=
and defines y<br>
=A0=A0 =A0=3D 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>=A0=A0 =A0function =
into G.<br><br>- A secret x could be shared (For example using Shamir secre=
t sharing), and<br>
=A0=A0 =A0every party gets a private share of the secret. Thus party P_i fo=
r example<br>=A0=A0 =A0gets its share x_i of the secret. <br>=A0=A0 =A0<br>=
- Because of the very simple structure of the signature, it is possible to<=
br>=A0=A0 =A0combine signature shares of the form (H(m))^x_i together using=
lagrange<br>
=A0=A0 =A0interpolation to get the signature over the message m, which will=
result in<br>=A0=A0 =A0(H(m))^x.<br><br>My question about this scheme is a=
s follows: Do you guys know any good GDH (Gap<br>diffie hellman) groups tha=
t 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 articl=
e "Group-oriented (t,n) threshold<br>signature scheme and digital mult=
isignature" by L.Harn. <br>
<br>This article proposes some kind of modified ElGamal algorithm to be abl=
e to do a<br>similar trick, in order to acheive threshold signatures. My pr=
oblem here is that<br>I'm not sure whether this modification is somethi=
ng 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 Thresho=
ld 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 t=
he 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 prim=
e<br>numbers or any special number theoretical object. Thus it is far easie=
r to share<br>the secrets between the parties in the protocol in a distribu=
ted manner.<br>
<br>I am aware of some attempts in other articles to remove the trusted par=
ty out of<br>the pre-setting of secrets in Victor Shoup's Threshold Sig=
nature, however it<br>seems to be very communication Expensive, much more t=
han 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 hap=
pen to know about working code on this subject, or an idea about<br>impleme=
nting 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>Regard=
s,<br>real.<br><br></div>
--001a11c24b0a69c68204eafe40f8--
--===============1918693476352794510==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============1918693476352794510==--
