Alternative multi-signature constructions

[burdges]

I think before either #6 or #12 or #11 we should believe that our multi-signature scheme is actually optimal, subject to being provably secure from some reasonable assumptions. I've implemented the most current protocol from the literature, but..

I've recently heard rumors that nicer schemes might be coming down the pipe. I'll provide a vague guess about their structure: All signers possess two signing keys pk1 and pk2 with the aggregate public key being H1(pk1,pk2,R)*pk1 + H2(pk1,pk2,R)*pk2, so the per-message signing key depends upon R. We create a multi-signature by running a two round multi-signature on both pk1 and pk2 separately, perhaps with the same R, and then computing this linear combination. In so doing, we might somehow insulate against the attacks from https://eprint.iacr.org/2018/417

I've no idea if anything upcoming really gives two rounds multi-signatures, but these rumors provide a reason to drag our feet on developing user interfaces that require three rounds.

[burdges]

It appears this might refer only to DG-CoSI mentioned in section 6.3 of https://eprint.iacr.org/2018/483.pdf and suggested as secure in old versions of https://eprint.iacr.org/2018/417.pdf but now that paper clarifies matters on page 3.

Instead, there is the two round mBCJ scheme on pages 21 and 21 of https://eprint.iacr.org/2018/417.pdf which we should probably implement. I've opened #15 which supersedes this issue.