Subject: [Cfrg] Scalable collective signing

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

To the list of desirable and perhaps required properties for any CFRG signature scheme, I would propose adding “compatibility with efficient threshold- and multisignature techniques.”  This requirement is easy to meet and probably already satisfied by most of the signature schemes proposed so far, but I would suggest this as perhaps one more reason to prefer Schnorr-based schemes over ECDSA-style schemes.  (Yes, there are threshold/multisignature schemes for ECDSA, but they’re complex and hard to scale.)

For anyone interested, my group at Yale (soon to be EPFL) has been working on techniques to make threshold/multi-signature protocols scale, making it possible to build attestation and signing collectives “as large as might be needed.”  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.  While large-scale collective signing is irrelevant for many uses of signatures (such as TLS endpoints, which may be this group’s primary focus), scalable multisignatures may be useful in building more trustworthy public logging, timestamping, certificate-signing, and other “authority” type protocols where we’d like to distribute trust across as large and diverse a group as possible.

More details of our ongoing work 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

The prototype code 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.  I’ll be at IETF 93 and am happy to discuss further with anyone interested.

Thanks
Bryan

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 12 Jul 2015 19:31:56 +0300

On Sun, Jul 12, 2015 at 10:28:21AM -0400, Bryan Ford wrote:
> To the list of desirable and perhaps required properties for any
> CFRG signature scheme, I would propose adding “compatibility with
> efficient threshold- and multisignature techniques.”  This
> requirement is easy to meet and probably already satisfied by
> most of the signature schemes proposed so far, but I would suggest
> this as perhaps one more reason to prefer Schnorr-based schemes
> over ECDSA-style schemes.  (Yes, there are threshold/multi-
signature schemes for ECDSA, but they’re complex and hard to
scale.)

Do those also work properly for (point,scalar) type schnorr
schemes?

The idea of those is essentially:

R = rG (r should be generated pseudorandomly).
s = r + H(R,M)*a, where a is the signing key.

3 of the 5 proposals are of that type. One is classic
Schnorr and one is very close to ECDSA.

-Ilari

---

From: Watson Ladd <[email-masked]>
Date: Sun, 12 Jul 2015 09:40:15 -0700

> Schnorr and one is very close to ECDSA.

Yes: If we generate e=H(R,M), s=r+H(R,M)*a as in the usual
presentation of Schnorr, R is recoverable as sG-eA. Since this
transformation involves only public data, it can be done as the last
step.

Sincerely,
Watson
>
>
> -Ilari
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Bryan Ford <[email-masked]>
Date: Sun, 12 Jul 2015 14:18:34 -0400

On Jul 12, 2015, at 12:40 PM, Watson Ladd <[email-masked]> wrote:
> <[email-masked] <mailto:[email-masked]>> wrote:

Indeed, although our current prototype code produces the traditional (scalar,scalar) challenge-response format signatures, I can’t think of any reason producing (point,scalar) format signatures would be problematic.

To help understand and evaluate the (current and future) signature proposals on the table, would it perhaps be useful to identify a few specific, preferably mostly orthogonal properties that can be discussed independently, so that if consensus is reached on some of them this can be used to “prune the design space” and focus attention?  I would immediately suggest considering these two:

1. Does it make sense to consider restricting attention to Schnorr-class signature schemes in general, as opposed to say ECDSA, RSA, pairing-based schemes, etc.?  There seem to be many reasons (efficient multisignatures being only one) to prefer Schnorr-class schemes over the others I’m immediately familiar with.  Are there readily identifiable, compelling advantages other non-Schnorr-class schemes have (e.g., ECDSA) that are relevant to the goals of this WG?

2. In evaluating Schnorr-class schemes, does it make sense to consider restricting attention to (point,scalar)-format signatures?  Although I don’t think it matters one way or the other for multisignature compatibility, the (point,scalar) format seems to have other benefits, efficient batch verification for one thing.  Are there any known advantages to the alternative (scalar,scalar) challenge-response format?  (I’m not immediately aware of any but am not exhaustively familiar with the relevant literature.)

I’m not suggesting that either these or other similar decisions should be taken quickly or lightly, but where there already seem to be clearly-identified advantages like the above in going one way over others, trying to reach consensus on those early-on might be useful.

Cheers
Bryan

>> [email-masked] <mailto:[email-masked]>
>> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>
> 
> 
> 
> --

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 12 Jul 2015 22:38:00 +0300

On Sun, Jul 12, 2015 at 02:18:34PM -0400, Bryan Ford wrote:
> 
> To help understand and evaluate the (current and future) signature proposals
> on the table, would it perhaps be useful to identify a few specific, preferably
> mostly orthogonal properties that can be discussed independently, so that if
> consensus is reached on some of them this can be used to “prune the design
> space” and focus attention?  I would immediately suggest considering these two:

I don't think those would prune the design space very effectively.

> 1. Does it make sense to consider restricting attention to Schnorr-class
> signature schemes in general, as opposed to say ECDSA, RSA, pairing-based
> schemes, etc.?  There seem to be many reasons (efficient multisignatures
> being only one) to prefer Schnorr-class schemes over the others I’m
> immediately familiar with.  Are there readily identifiable, compelling
> advantages other non-Schnorr-class schemes have (e.g., ECDSA) that are
> relevant to the goals of this WG?

Well:
ECDSA: Compatiblity is explicitly non-goal (one of the proposals is this
       style).
RSA: I don't think that is ECC signature scheme.
Pairing-based: I don't think it works with "natural" curves.

So I don't think there are identifiable advantages.

> 2. In evaluating Schnorr-class schemes, does it make sense to consider
> restricting attention to (point,scalar)-format signatures?  Although I
> don’t think it matters one way or the other for multisignature
> compatibility, the (point,scalar) format seems to have other benefits,
> efficient batch verification for one thing.  Are there any known
> advantages to the alternative (scalar,scalar) challenge-response
> format?  (I’m not immediately aware of any but am not exhaustively
> familiar with the relevant literature.)

AFAIK, can be put into less space by truncating the hash (although
IIRC DJB says there is not enough security analyis for that).

-Ilari