[curves] Threshold ECDSA / comparison to Schnorr

[Trevor Perrin]

On Sun, Mar 22, 2015 at 1:29 PM, Gregory Maxwell <gmaxwell at gmail.com> wrote:
> Trevor Perrin wrote:
>> In particular:  Does Schnorr still hold an advantage in this area, or
>> has ECDSA closed the gap?
[...]
> Assuming all is good with respect to dealerlessness, there are two
> primary problems which leave it significantly disadvantaged compared
> to Schnorr in my view:
>
> (0) Signatures require 3*t - 2 rounds of communication.  Imagine each
> of the participants prudently keep their signing device in a safe and
> are using asynchronous communication to perform their signature (e.g.
> emailing around a invoice to sign off on; or a new software release.).
> Going back and forth to make multiple communication rounds is quite
> burdensome.

Fair point - if signers are physically separate and offline,
communication rounds could be worth minimizing.


> [Pieter Wuille has an implementation of plain schnorr threshold
> signatures for libsecp256k1, I'll prod him to post it... it's quite
> small.]

Yeah, it would be great to see it, and hear any lessons-learned or tradeoffs.

On a side note this list has discussed 25519 and Goldilocks and
similar curves, but has had no discussion of the Bitcoin curve
(secp256k1).

Many people - like myself - know very little about it.  For example, I
have no idea how it stacks up to, say, 25519 in performance, security,
and quality of implementations.  Does anyone?


> There is a more meta-issue which is maybe only of great interest in
> the Bitcoin space that is a mark against any traditional threshold
> signature, which is the issue of accountability.  While efficiency is
> important,  it is also often important that the participants be able
> to inspect a signature after the fact and prove which of the
> participants signed.

There's some literature on "threshold signature scheme with traceable
signers", is that what you're after?


> With respect to indistinguishably, this can also be achieved by
> smaller thresholds just filling in dummy additional keys (and defining
> in your system that true one of one) is not permitted.

Could you expand on that?  I would think any scheme with
multi-signatures and dummy keys has a risk of becoming
"distinguishable" over time based on multiple observations of which
keys are signing?


Trevor