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

From: Bryan Ford <[email-masked]>
Date: Sun, 12 Jul 2015 10:28:04 -0400

Hi TRANS folks,

My group at Yale (and shortly to be at EPFL) has been working on techniques to make threshold/multi-signature techniques scale efficiently, a goal partly motivated by the CA security problem, and whose solution may be relevant and complementary to CT.  Basically, our protocol allows a “authority server” of any kind to propose publicly a message to be signed, and any number of “witness” nodes get the opportunity to inspect and approve or object, in the former case contributing a share of the final signature, ensuring that nothing gets signed without being widely witnessed and approved.  For example, in testbed experiments we’ve demonstrated ~4000 participants collectively computing a single signature in 1.5-3 seconds including wide-area-equivalent round-trip times.  I envision this capability might be useful to the TRANS group’s goals in various ways:

1. In the long term - most ambitious but perhaps least realistically deployable - security-conscious CAs could in the future move toward a collective-signing model for issuing actual certs.  For example, root CAs could gradually deprecate the issuance of delegated authority to sub-CAs, instead bringing these sub-CAs into a collective run by the root, such that any CA in the group can propose certificates but all have the opportunity to inspect before the cert receives a valid (collective) signature.  Of course there would be many practical challenges here; I’m under no illusion that this approach would be viable for the near-term but may be worth thinking about on a “long-term roadmap.”

2. A more near-term possibility is to consider collective signing for SCTs in CT.  This would be easier to deploy incrementally since CT isn’t yet “set in stone”, but it would still present challenges, such as the possibility of delaying SCT signatures (even if by only a few seconds), to which there may be objections.

3. A still more near-term possibility is to consider enhancing CT log-servers to support collective signing of log-heads.  Witness/monitor servers would then be able to join the signing collective of log servers they monitor, not just passively checking but actively contributing to the signature of each log-head signature.  Anyone (particularly clients) could then check offline that a log-head was not only signed by the log server operator but also witnessed and verified by any number of monitor servers with a single signature check.

Regardless of approach, I think the most important potential opportunity here is to address the privacy problem that CT’s gossip mechanism creates for clients.  Currently clients have no way to check the SCTs they see unless they’re willing to reveal their browsing history to a “trusted monitor”, which is unfortunate for users desiring privacy and reluctant to trust any single “trusted authority".  With either options #2 or #3 above, a client could verify that an SCT was signed (#2) or a cert was logged and widely witnessed (#3) with a single signature-check requiring no communication or browsing-history disclosure to any server.

At the moment I just want to bring this information to the group and solicit feedback or discussion for anyone interested; I’m not making any particular proposal at the moment.  If collective signing support provides to be of interest at some point, it could certainly be added as a later-stage CT extension.  The main (and only that I know of now) consideration I suggest the group might want to consider in the near term is whether the CT spec should perhaps include support for at least one Schnorr-type signature scheme (e.g., Ed25519) rather than just RSA and ECDSA, since scalable multisignatures work readily in Schnorr schemes but are not so easy or scalable in RSA or ECDSA.

We did a short presentation recently at HotPETS on this topic, and I would be happy to do a brief presentation on this at the TRANS meeting if there’s time and interest.  More details of this ongoing work-in-progress are available in the following preprint and slide-deck:

	Decentralizing Authorities into Scalable Strongest-Link Cothorities
	Preprint: http://arxiv.org/abs/1503.08768
	Slides: http://dedis.cs.yale.edu/dissent/pres/150610-nist-cothorities.pdf

Our prototype code (in Go) is also online and I’d be happy to share it, but it’s not yet in a particularly clean, well-documented, or usable state yet.  We’ll be working on that over the coming months but am happy to work with anyone deeply interested enough to want to dive into the code earlier.  And in any case, I’ll be at IETF 93 for the whole week and happy to discuss further with anyone interested.

Thanks
Bryan