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

[Tom Ritter <[e-mail]>]

Thanks for this, I was pretty far off from my assumptions!

On 22 October 2015 at 09:59, Bryan Ford <[e-mail]> wrote:
> No, at least in its current form there is technically particular threshold that needs to be decided on ahead of time, left unchanged, or even agreed on by everyone.  The leader/proposer (e.g., log server) produces a message, collects “partial signatures” from any subset of the M co-signers it deems to be online and available, and works with them to produce a collective signature that documents exactly which subset of the M potential co-signers was actually present and contributed to the signature.  By implication, it’s obvious from the collective signature how many of those co-signers were present, so if the leader (perhaps maliciously) tries to leave a bunch of honest participants out in one or more rounds, there’s lots of opportunity for anyone to notice and ask questions.
>
> In essence, the collective signing protocol as it stands produces something semantically equivalent in information content to up to M individual signatures, but merely “optimised” for a full rather than empty set of co-signers.  If all M signers are online and participating in a given signing round - as I would hope and expect to be the expected normal operating practice - then the collective signature is basically equivalent in size and verification cost to a single individual signature.  The size and verification cost of the collective signature then basically increases as more and more nodes “go missing”, basically because the collective signature needs to include (verifiable) metadata about the missing nodes allowing signature verifiers to “subtract out” those nodes’ components of the composite public key.  In the worst case, if the leader really wants to produce a collective signature with only 1 or 2 nodes actually participating, then the collective signature will get big. :)


Oh.  Really cool!  I think the larger size of signatures might be an
issue for SCTs, but like you mention, doing it for STHs seems quite
reasonable!


> No one needs to generate key pairs on behalf of everyone else: all participants generate their own key pairs independently and keep the private parts secret, just as in the M-individual-signatures case.  The main restriction is those keys all have to be generated in an agreed-upon cryptographic group: e.g., P-256, or P-something-else, or Ed25519 or Goldilocks.  Since elliptic curves used for signing are pretty standardised anyway (unlike the DSA practice of having new group parameters for each key pair), this doesn’t seem like a significant issue.


Agreed; nice!


> I’m assuming the members of M are reputable, relatively stable independent organisations who are able and committed to keep servers alive at least most of the time, so that it should be a fairly exceptional event (and a moment of public shame!) for such a witness/co-signing server to go AWOL even for one signing round.  Of course an organisation running a witness server could just suddenly go belly-up or decide to stop providing service without notice, but that will just mean that a “witness 15 was missing” metadata record will be present in each collective signature record signed with that group configuration until the next time the group configuration is updated.


I am less sure about that.  The more expectations placed on an
organization around uptime and reliability - the fewer organizations
you'll have participating.  I have to think a more successful model is
"Run this software for a month, get used to it, and then we'll add
you.  Keep it up as best you can, and if you have problems keeping it
up, we might remove you on our quarterly membership changes."


> I envision the group configuration being updated not too often, e.g., preferably like once a year or at most once every few months.  One obvious avenue for group configuration updates is simply to handle them the same way that updates to root CA certs, root log server certs, and other roots of trust are handled in web browsers: i.e., just align root-configuration updates with the software update cycle.
>
> Would a witness group configuration need to be “valid for 3 years” like root certificates?  That’s one possibility that might not be unreasonable, but collective signing gives us other interesting and potentially better alternatives.  For example, if a witness group’s composition changes every year or every quarter, then the last thing the leader might do in the prior group configuration is use it to collectively witness and sign a successorship record, stating what the next group configuration record is.  The successor group configuration can have not only added and/or removed members, but also all the remaining members can generate brand-new key pairs for each successive group configuration, and those participants can immediately scrub the private keys they were using in the prior configuration.  Clients who might be running months- or years-old web browser versions or whatnot can still “chain forward” by following multiple such successorship links from the last configuration they know and trust to the latest configuration.  This would thus not only ensure that old clients can transition to new roots of trust more seamlessly than they do now, but would also allow all the keys used in collective signing to have more like 1-year (or 3-month) lifespans rather than the currently typical 3-ish-year windows.

Chaining is good, requiring software updates doesn't seem very good.


>> Also, the slides mention "1-of-k" but I assume it's truly N-of-M and
>> not 1-of-M correct? Because we should assume at least 1 if not a few
>> orgs will have their key share compromised and we need to set N high
>> enough that the average security of the group of organizations is high
>> enough that compromising N orgs would be difficult.
>
> Hmmm, could you point out which slide you’re referring to?  Might be a typo.

Can't find it, must have gotten confused about your intro slide.