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). _______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves