[148145] in cryptography@c2.net mail archive
Re: [Cryptography] Practical Threshold Signatures
daemon@ATHENA.MIT.EDU (Bear)
Tue Nov 12 19:31:21 2013
X-Original-To: cryptography@metzdowd.com
From: Bear <bear@sonic.net>
To: realcr <realcr@gmail.com>
Date: Tue, 12 Nov 2013 13:36:00 -0800
In-Reply-To: <CAE8kFFBrygG+B9DjTrZxEBTaKRpXEjVgvuoX5NcX-Y7q30sPPg@mail.gmail.com>
Cc: cryptography@metzdowd.com, cryptography@randombit.net
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
On Tue, 2013-11-12 at 19:33 +0200, realcr wrote:
> 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?
For me, it always made sense to think of threshold schemes in terms
of geometry. For example, if you want a situation where any two of
some number of people must cooperate in order to produce a key, you're
looking for an entity which can be defined by any two of some other
class of entities.
In geometry, a point can be defined by the intersection of two lines.
So if you give each of your N participants a subkey that corresponds
to a geometric line, and all the lines intersect at some point, then
the point can be taken as the key to unlock the secret. However, this
particular construction gives each participant the ability to reject
all false keys that don't appear at points along his "line"; given any
proposed key and any two subkey holders, it is certain that unless it
is the correct key, one of them will be able to tell it is the incorrect
key without the cooperation of any other. You may want that property
for some specialized protocols, but not for the most general use.
So, instead, you could let each subkey represent a point along a line,
and then let the full key be the Y-coordinate at which the line
intersects the x-axis. This has a different property in that every
possible full key remains possible as far as any subkey holder knows,
regardless of the value of their own subkey. And that's a 2-holders
scheme suitable for a different (and more general) set of protocols.
Likewise, if you're looking for a key that can be determined using
any three subkeys, you can let the subkeys represent lines, and then
let the key represent the center point of the circle tangent to all
three lines. But again, this provides the holders of any two
subkeys with the power to discriminate between a large set of
impossible keys and a set of possible keys, which, again, is only
useful in some limited protocols.
Generalizing again, you can let each subkey be a point along a circle,
and put them together indicating the full key at the point where that
circle intersects the X-axis. In this way you again create the
situation where given any two subkeys, you cannot eliminate any
possibility for the value of the full key until you are given a third
subkey.
Alternatively, you can go with the first scheme (in which each subkey
is a line and you're determining a circle tangent to each of three lines
to find the full key) except that the full key is the *radius* of the
circle instead of the *centerpoint* and you'll have the same desirable
property of requiring all of three keys to eliminate *any* possible
value for the full key.
Anyway, I don't know how many people's brains work in exactly this way,
but this has always been an easy mental tool for me to envision and
develop secret-sharing schemes. It gets a bit less obvious as it goes
into higher share numbers, but there's a very natural set of geometric
relationships where a line can be defined by two points, a plane or a
circle by three, a sphere or conic by four, etc, and it isn't at all
difficult to generalize into higher dimensions.
Bear
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography