[curves] Threshold ECDSA / comparison to Schnorr

[Gregory Maxwell]

Trevor Perrin wrote:
> In particular:  Does Schnorr still hold an advantage in this area, or
> has ECDSA closed the gap?  What are the differences with respect to:
> - trust assumptions (trusted setup, robustness to misbehaving parties)
> - communication costs (in particular, # of rounds)
> - computation costs
> - implementation complexity

I comment some about this latest work on Bitcoin Talk... I'll repeat
my thoughts that don't really duplicate the comments so far...

The published implementation (hurray!) does not implement a
dealer-less protocol (boo).  The authors of the paper claim that a
dealer-less protocol is possible (hurray).

Without a dealerless protocol I consider threshold signatures to be of
fairly little value. If you have a trusted dealer to initially create
the key material then you can simply keep the key in that dealer.

[This isn't _always_ true, but it's close... at least in Bitcoin we
largely look to threshold cryptography as a mechanism to overcome the
practical impossibility of ensuring a single party or single
implementation is free of backdoors or has perfect immunity to
coercion.]

The same authors prior work also claimed to be dealerless (and did so
in response to my disbelief at a workshop where they discussed it
prior to publication) and I wasted quite a bit of time trying to
implement it and feeling stupid when I couldn't figure it out, until I
later found they published an erratum that their prior work could not
be used dealerlessly.  So, analyzing a dealerless implementation this
time is not high on my priority list. (I spent some time trying to
phrase this as anything but a whine, but couldn't. Take it for what
its worth.). I hope someone else does it!

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.

Extensive interaction would be acceptable for one time init (and
probably would be required for a dealerless init), but would be quite
painful for each signature in this case.

Schnorr can do one-pass signing if R values were pre-established one
time in an interactive init-phase (though this requires state to avoid
R reuse); or two passes for any threshold size without state and
interactive setup (one pass to get the R each signer will use, another
to sign).

It may be the case that some interaction could be moved to one time
setup in this new threshold ECDSA, but it wasn't immediately obvious
to me how to do so.

(1) Requires a _substantial_ amount of additional cryptographic code.
Schnorr multi-signature requires only a few dozen of additional code,
and no additional low level code over basic signature generation code
(e.g. no more bignum, no extra field arithemetics.)... as it needs
paillier  homomorphic encryption, which is implemented on a different
group.

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

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.

Consider, you secure some funds so that two of three of you, your
aunt, and your attorney must sign off.  Later the funds are stolen.
You protest that your attorney has violated your agreement and seek to
damage his reputation in response (or try to take him to court); he
counters that he didn't sign and you must have been hacked / must be
lying.

(in other words, even a one time signature still exists in a
persistent universe :) ).

I have two different 'efficient' schnorr-based signature schemes that
are accountable,  but they're less efficient, instead of O(1) sized
signatures, one has O(log(binomial(n,m))) sized signatures and the
other has signature size which is O(n-t') where t' is the number of
non-participants (more than the threshold can participate to reduce
the signature size; and if the actual threshold is smaller than the
number of signers it can be kept secret, so a 1 of 1 with this scheme
looks just like a 90 of 100 when 100 actually sign). (Both also
require no interaction to establish the public key, which is also a
consideration, and both have verification performance similar to a
single signature).

(There is also a third less efficient semi-multisignature which is
accountable with a signature size which is 32*N + 64 bytes (for a
32-byte group), and almost as fast as a single signature... requires t
additional y recoveries and t additional ge/gej additions).

I've still not been able to come up with an accountable plain discrete
log scheme with O(1) sized signatures.

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.  "Meh.".  It's
a nice property, but I don't know that it outweighs accountability
considerations. (especially compared to the above scheme I mentioned
which looks like a smaller count-threshold difference so long as a
larger number of signers participate).