Subject: [Cfrg] Schnorr multisignatures on Ed448 and Ed25519

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 7 May 2019 17:45:59 -0400

There is a lot of interest in the bitcoin world about the use of Schnorr
multi-signatures and was a recent conversation on the cryptography list on
these. My position is

1) I want to use them or something like them in my design for the Mesh.

I would very much like to have the ability to safely split the generation
of signatures between two different signers so that both signers must use
their parts of the key to generate a composite signature but this does not
reveal any information that might help either party generate signatures for
other documents or perform any other activity related to the composite
private key.

2) I have neither the time nor the expertise to arrive at a sufficient
degree of confidence that the construction is secure.

3) If we don't do it right or tell people it is a bad idea, they are
certain to do it and do it wrong.

Are there any academics who are interested in doing this analysis and
producing a draft that either explains a safe means of creating an Ed448
signature using private keys a, b such that they can be verified with key
A+B or tells us why this is a bad idea?

My concern is of course that El Gamal Signature is a tricky beast and if
you leak certain information used to create one signature, you can enable
an attacker to create other signatures or even disclose the private key.

I am already making use of the key co-generation scheme I described at a
CFRG in Prague some years back. It allows me to make use of manufacturer
generated keys on IoT devices without giving the manufacturer a backdoor.
But the approach I am using right now requires me to join the two parts of
the private key to make use of it. This means I cannot use a manufacturer
provided hardware bound key for signature operations.

---

From: Taylor R Campbell <[email-masked]>
Date: Tue, 7 May 2019 22:03:29 +0000

> Date: Tue, 7 May 2019 17:45:59 -0400
> From: Phillip Hallam-Baker <[email-masked]>
> 

In the usual naive way to do this, if Alice publishes A = a*G as her
public key, Bob can publish B - A for B = b*G as his public key and
thereby unilaterally sign messages that pass verification under the
public key A + (B - A) = B.

There's been a spate of papers in the past couple of years on
threshold signature schemes, some (all?) of which avoid this at some
cost, including CoSi, MuSig, and mBCJ.  There was an internet-draft,
draft-ford-cosi-cfrg, but it didn't seem to go anywhere.

The problem seems to be complicated, but it would be nice for the
internet to have a good standard threshold signature scheme -- ideally
without changes to verifiers -- and to get away from foolhardy
applications of secret-sharing that inherently leave some party with
unilateral signing power at some stage.