Re: [Trans] Long-term: scalable collective signing (of certs, log-heads, and/or SCTs)

[Bryan Ford <[e-mail]>]

On 30 Sep 2015, at 21:00,Katriel Cohn-Gordon <[e-mail]> wrote:
> 
> ​Note that ARPKI <http://dl.acm.org/citation.cfm?id=2660298> (among other academic CT variants) similarly has no need for gossip; roughly, monitors sign that they have seen a cert and then clients just verify the signatures. Multisignatures sound like an elegant way to achieve that; are they more efficient than n individual signatures for smallish cothorities e.g. size <10?

Yes, a bit more efficient but the difference isn’t necessarily a big deal in practice for n ~ 10.  

We now (in just the past few weeks) have some better comparative experimental results on this; see pages 35 and 36 of the following slide deck:

	http://dedis.cs.yale.edu/dissent/pres/151009-stanford-cothorities.pdf

The green line and area is the signing latency of our collective signing protocol, now consistently under 2 seconds while scaling all the way out to 8192 hosts.  

The red line is the performance of the basic approach of simply collecting a lot of individual signatures.  As you can see it works fine for small n (and in this case signing latency is lower until the crossover point of about 128 participants.  But computation costs - most of which is signature checking, which signature-verifying clients would have to do as well - increases much more rapidly even for small numbers of hosts (slide 36).

Finally, the blue line shows the even worse scalability of classic multisignatures based on Joint Verifiable (Shamir) Secret Sharing (JVSS or JVSSS, depending on how much you like S’s).  The key problem there is that to avoid depending on a “trusted dealer”, every signing round requires every participant to deal a polynomial with shares for every other, then everyone must verify and combine these O(N) polynomials each of size O(N) into one master polynomial, etc., producing O(N^2) for everyone on each round.

At the talk above I recently gave at Stanford, Dan Boneh made the helpful observation that this O(N^2) per-signature cost of dealing fresh secrets in every round could probably be avoided through the use of a suitable pairing-based signature scheme such as BLS (https://en.wikipedia.org/wiki/Boneh–Lynn–Shacham).  Thus, after paying the O(N^2) as a one-time cost only on group setup, more traditional threshold crypto methods might become a more viable alternative in terms of per-signature costs.

Using traditional threshold crypto would have somewhat different properties that may be desirable in some situations and undesirable in others.  On the upside, the signatures produced would always be exactly the same size and always verifiable using exactly the same process no matter how many co-signers were actually online and participating in any given round.  On the downside, the signatures produced would not contain information “publicly documenting” which signers actually did or did not participate in each round, a property that seems undesirable in transparency-oriented situations like this.  Also, the threshold would have to be fixed and decided in advance, and a “signing threshold of zero” (ensuring that the primary signer can make progress no matter how many co-signers are missing) would not be an option.

Cheers
Bryan