cosi: consider delinearization schemes to increase robustness to related-key attacks

[bford]

The current CoSi design requires that the holders of public keys used in a collective signature prove ownership of the corresponding private key, e.g., via a self-signed certificate, to ensure that a member of a collective signing group cannot pick a public key maliciously so as to cancel out the contributions of other, honest "victim" members of the collective signing group. This is currently discussed in section 8.5 "Related-Key Attacks" and mentioned more briefly earlier in the document.

However, there are ways to increase the signing scheme's robustness to such related-key attacks even if parties relying on the collective signatures do not check self-signed certificates for all members of a collective signing group: see for example "Schnorr Multisignatures for Bitcoin" by @sipa. There are multiple such potential related-key-attack-hardening designs to be considered, with different tradeoffs. Perhaps the main discussion should be held on the CFRG mailing list if/when collective signing becomes a CFRG WG item, but further thoughts and other relevant background references are welcome here as well.

See also bford/golang-x-crypto#1 by @prusnak

[bford]

Note that I've just opened up another Issue, perhaps more of a "meta-issue", to elaborate and try to more carefully organize a list of discussion points including this one: see #2

[bford]

More related background discussion from bitcoin-tak, thanks @oleganza for the pointer

[sipa]

In particular, with a requirement for pre-certified keys, multisignatures are unusable for signature aggregation in Bitcoin (see the bitcointalk link above), as the choice of signers is done by the attacker, not ahead of time.

Perhaps the main scheme to consider is Bellare-Neven multisignatures (https://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf). This is proven secure against related key attacks (called rogue key attacks in their paper), and thus works without any published self-signatures. The signing step should be similar in performance, but validation would require an EC multiplication per effective signer. This is a slowdown for validation as such, but not when including the time to validate the possibly necessary self-signatures.

Instead of each participant producing a partial signature (nonce - privkey*H(combined_pubkey || nonce*G || msg), they produce a (nonce - privkey*H(H(pubkey1 || pubkey2 || ...) || pubkey_n || nonce*G || msg). The validation equation is updated similarly (which can no longer be written as the validation of a single signature with a combined public key).

Thanks to the anonymous reviewers of our BITCOIN17 paper on multisigning to refer us to that work.

[bford]

Thanks Pieter for the background pointers. Yes, I think I've seen the Bellare-Neven multisignatures paper before, somewhere, but not recently. That's definitely extremely relevant, and good to know there's a formal correctness proof for this variation.

The need for a separate scalar multiplication per cosigner is a pretty unfortunate cost, though, which could make a significant difference when the number of cosigners is large. Although we haven't actually benchmarked it yet, my guess is that this would pretty much eliminate the performance advantages of collective signing (over a simple collection of individual signatures), leaving only the space-compactness benefit.

The key question is whether the benefit of this type of construction justifies its cost, which is a topic that I think we'll want to discuss on the CFRG list if/when we can get the working group to adopt collective signing as a work item. If you would support such an effort in general, it would be great if you could post a brief note to that effect on the CFRG list. Thanks again!