[Cryptography] Practical Threshold Signatures

[Bear]

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