Quote from: earonesty on August 28, 2018, 10:25:36 PM

Each party interprets the public keys as shares in a Shamir sharing scheme. Put simply, lagrange coefficients are calculated using Xi = H(G*xi). The coefficients are ordered, based on the sort order of X.


for i1 in sorted(Xis):
    coeff[i1]=1
    for i2 in Xis:
        diff = (i2-i1)%P
        inv = modinv(diff, P)
        val = i2 *inv%P
        coeff[i1]=coeff[i1]*val%P

These coefficients are used to multiply each point by. The results are summed, and that is the bitcoin public key the key that these participants are signing for.

As has been explained to you previously: This is insecure for large enough M. You have key P1, the attacker claims to be persons P2 ... Pn and selects them adaptively so that sum(P1 .. Pn) = P1 + xG - P1 = xG, where x is some attacker controlled secret. They do this by computing a collection of dummy keys Dq = q*P1 and setting Fq = 1/q * H(q*P1) then using Wagner's algorithm to find a subset of Fq values that sum to -H(P1). P2 ... Pn-1 are Dq from solution and Pn is just some attacker controlled key. As n grows to some small constant in the number of bits in the key sizes, finding the subset sum becomes computationally cheap.

Quote

Currently, the leading proposal for a multisignature scheme is an M of M scheme

No, it is not. The BIP for it explains how verification and simple signing work, but the scheme works fine for arbitrary montone functions of keys (including arbitrary thresholds).

Quote

that provides both aa noninteractive M of M scheme

This is inconsistent with your above claim:

Quote

The value of e must be the same for all participants.

Quote

When signing, each participant i rolls a random nonce ki. ... R = G*k; e = H(R, M, X)

So either R in the H() above is the sum of participants Rk_i, or e is different for each participant.

If it's the first case, the signature requires a round of interaction to learn the combined R before they can compute s. If it's the latter the signature is not additive homomorphic and your verification will fail.

Also, if it's the former-- R = sum(Rk_i), then an attacker can set their Ri to be kG minus the sum of all other Rs, resulting in a signature where they know the discrete log of R with respect to G (k), and can recover the group private key x as x = (s - k)/e.